Suppose you are choosing between the following three algorithms: 1) 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.
2) Algorithm B solves problems of size n by recursively solving two subproblems of size n - 1 and then combining the solutions in constant time.
3) 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?
a) This is a case of the Master theorem with a = 5, b = 2, d = 1. As a > b^d, the running time is O(n^logb a) = O(n^log2 5) = O(n^2.33).
b) T(n) = 2T(n−1)+C, for some constant C. T(n) can then be expanded to C * the summation from i = 0 to n−1 2^i+2^n * T(0) = O(2^n).
c) This is a case of the Master theorem with a = 9, b = 3, d = 2. As a = b^d, the running time is O(n^d log n) = O(n^2 log n).