Master theorem

Questions 1 to 5 of 7

1. 1. What is the running time of T(n) = 2 T(n/2) + n?

   Θ(n)Θ(n log n)Θ(n^2)Θ(log n)
2. 2. What is the running time of T(n) = 2 T(n/2) + n^2?

   Θ(n log n)Θ(n^2 log n)Θ(n^2)Θ(n^3)
3. 3. What is the running time of T(n) = 4 T(n/2) + n^2?

   Θ(n^2)Θ(n^4)Θ(n^2 / log n)Θ(n^2 log n)
4. 4. What is the running time of T(n) = 2 T(n/4) + sqrt(n)?

   Θ(sqrt(n) log n)Θ(sqrt(n))Θ(n log n)Θ(log n)
5. 5. For T(n) = T(n - 1) + n, why can the master theorem not give the answer directly?

   The critical exponent is 1, and the rule works only when it is 2.The input shrinks by subtracting 1, not by dividing by a fixed factor b, so the recurrence does not have the form a T(n/b) + f(n).f(n) = n is not a power of n.a is 0, so the rule would divide by zero.