Suppose you are choosing between the following three algorithms: Algorithm A sol

Question

Suppose you are choosing between the following three algorithms: Algorithm A solves problem 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 u by recursively solving two subproblems of size (n - 1) and then combining the solutions in constant time Algorithm C solves problem ot size n by dividing them into nine subproblems of size n/3, recursively solving each subproblcm and then combining the solutions in 0(n2) time What are the running times of each of these algorithms (in big-O notation), and which one would you choose

Explanation / Answer

a) Expression will be T(n) = 5 T(n/2) + n by Master's theorm b=5 a=2 so T(n) = n ^ lg5 b) Expression will be T(n) = 2 T(n-1) +c At each level, we getting double sub problems, like 2,4,8.. so it will be of O(2^n) c. Expression will be T(n) = 9 T(n/3) + n^2 so b=9 a=3 log3(9) = 2, which is equal to power of constant term so it will be O(n^2 log n)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---