Chapter 2: Q4E (page 83)

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 $n - 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 $n / 3$ , recursively solving each sub-problem, and then combining the solutions in $O (n^{2})$ time.
What are the running times of each of these algorithms (in big- O notation), and which would you choose?

Expert verified

Running time for each algorithm are:

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

Step by step solution

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.

Algorithm A will also be expressed as
$T (n) = 5 T (n / 2) + n$
by use of the Master's theorem
$b = 5 a = 2$
Thus, $T (n) = O (n^{l g 5})$
1. Algorithm B will be expression as
2. $T (n) = 2 T (n - 1) + 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 (n) = O (2^{n})$
1. For Algorithm C, calculation is based on question is given as above.
  $T (n) = 9 T (n / 3) + n^{2}$
  So,
$b = 9 a = 3 \log_{3} 9 = 2$
Which is equal to power of constant term
so run time will be: $T (n) = O (n^{2} \log n)$