Suppose you are choosing between the following three algorithms, all of which have 0(1) base cases for size 1: 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 one subproblem of size n/2, one subproblem of size 2n/3, and one subproblem of size 3n/4 and then combining the solutions in linear 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 0(n^2) time. What are the running times of each of these algorithms (in asymptotic notation) and which would you choose? You may use the Master Method. Hint: Approach Algorithm B via the substitution method. Formatted - pastebin. com/WqjWFtbM
Explanation / Answer
SOLUTION: A T(n) = 5 * T( n/2 ) + O(n) a = 5; b = 2; d = 1 (from general form) d 1 2 = log 9 b 3 2 so O( n log n ) ALGORITHM C is the best of the three