Master theorem in Python

Questions 1 to 5 of 7

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

   Theta(n log n)Theta(n^2)Theta(n)Theta(n^2 log n)
2. 2. What is the running time of T(n) = T(n / 2) + 1, the recurrence for recursive binary search?

   Theta(n)Theta(n log n)Theta(1)Theta(log n)
3. 3. What is the running time of T(n) = 2 * T(n / 2) + n^2?

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

   Theta(n^2)Theta(n^3)Theta(n^2 log n)Theta(n log n)
5. 5. T(n) = 2 * T(n / 2) + n. Which case of the master theorem applies, and why?

   Case 1, because f(n) grows more slowly than n^cCase 2, because f(n) = n matches n^c, where c = 1Case 3, because f(n) grows faster than n^cThe theorem does not apply, because n / 2 is not a whole number