Suppose you are choosing between the following three algorithms:
Algorithm A solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time.
Algorithm B solves problems of size n by recursively solving two subproblems of size n − 1 and then combining the solutions in constant time.
Algorithm C solves problems of size n by dividing them into nine subproblems of size n/3, recursively solving each subproblem, 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?
So, for A I guess thats O(n*log(n)), because of T(n) = 5T(n/2) + O(n)
For C, it should be O(n^2) - applying Master Theorem
And for B Im not quite sure since: We have a tree with n-depth. Just O(n)? Thank You very much :)
The recurrences for the algorithms $A, B$ and $C$ are:
$$ A(n) = 5A\left( \frac{n}{2} \right) + n $$ $$ B(n) = 2 B(n - 1) + 1 $$ $$ C(n) = 9C\left( \frac{n}{3} \right) + n^2 $$
The bounds of these recurrences are: $$ A(n) = \Theta\left(n^{\log_2 5}\right) $$ $$ B(n) = \Theta \left( 2^n \right) $$ $$ C(n) = \Theta \left( n^2 \log_3 n \right) $$
The most efficient algorithm in terms of complexity is $C$. Since you were unsure about $B$ we derive its solution. We expand the first few terms and find that:
$$ B(n) = 1 + 2 + 2^2 + 2^3 + 2^4 + ... + 2^n $$ $$ = \sum_{k = 0}^n 2^k = 2^{n - 1} - 1 $$
And so $B(n) = \Theta \left( 2^n \right)$. We can verify all bounds using induction.