Runtime of Recurrence relation [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 9 years ago.

Improve this question

Just had this on a quiz: T(n) = 4T(sqrt(n)) + 5

I simplified it using substitution and got F(k) = 4F(k/2) + 5

Using the master theorem I guessed it was O(logn). Is this accurate?

Answer 1

Define

F(n) = T(2^n)

Then we have that

F(n) = 4F(n/2) + 5

By the master theorem, we have that

a = 4
b = 2
f(n) = 5 = O(1) = O(m^0), so c = 0
0 < 2 = log_2(4)

So we're in case 1 of the master theorem. By case 1, we have

F(n) = Theta(n^2)

So

T(2^n) = Theta(n^2)

Therefore

T(n) = Theta(log(n^2)) = Theta(2logn) = Theta(log n)

So yes, your answer seems to be correct.