Question

Suppose you are choosing between the following three algorithms: • Algorithm A solves problems by dividing them into five sub-problems of half the size, recursively solving each sub-problem, and then combining the solutions in linear time. •

Algorithm B solves problems of size n by recursively solving two sub-problems of size $\mathbf{n}\mathbf{-}\mathbf{1}$and then combining the solutions in constant time. • Algorithm C solves problems of size n by dividing them into nine sub-problems of size $\mathit{n}\mathbf{/}\mathbf{3}$, recursively solving each sub-problem, and then combining the solutions in $\mathit{O}\left(n^2\right)$time.

What are the running times of each of these algorithms (in big- O notation), and which would you choose?

Short answer

Running time for each algorithm are:

• $\mathrm{T}\left(\mathrm{n}\right)=\mathrm{O}\left({\mathrm{n}}^{\lg 5}\right)$
• $\mathrm{T}\left(\mathrm{n}\right)=\mathrm{O}\left(2^{\mathrm{n}}\right)$

$\mathrm{T}\left(\mathrm{n}\right)=\mathrm{O}\left({\mathrm{n}}^2\log \mathrm{n}\right)$

Step-by-step solution

Basic information about each algorithm

Algorithmic A solves issues by breaking these onto five half-size sub-problems and systematically answering each one.

Algorithm B repeatedly tackles two sub-problems in size n to solve these issues of size n .

Algorithm C divides issues of size n over nine sub-problems with size n/3 and solves every sub-problem iteratively.

Running time calculation

1. Algorithm A will also be expressed as
   $T\left(n\right)=5T\left(n/2\right)+n$
   by use of the Master's theorem
   $$\begin{gathered} b=5 \\ a=2 \end{gathered}$$
   Thus, $T\left(n\right)=O\left(n^{lg5}\right)$
2. 1. Algorithm B will be expression as
   2. $T\left(n\right)=2T\left(n-1\right)+c$
      We're having multiple sub issues for every stage, like as 2,3,8,....
      So run time will be of order:

   localid="1659070651841" $T\left(n\right)=O\left(2^n\right)$

3. 1. For Algorithm C, calculation is based on question is given as above.
      $T\left(n\right)=9T\left(n/3\right)+n^2$
      So,

   $$\begin{gathered} b=9 \\ a=3 \\ {\log }_{3}9=2 \end{gathered}$$
   Which is equal to power of constant term
   so run time will be: $T\left(n\right)=O\left(n^2\log n\right)$