Can someone help solve this recurrence relation?

Question

T(n) = 2T(n/2) + 0(1)

T(n) = T(sqrt(n)) + 0(1)

In the first one I use substitution method for n, logn, etc; all gave me wrong answers.
Recurrence trees: I don't know if I can apply as the root will be a constant.

Can some one help?

Answer 1

Use Master Theorem to solve such recurrence relations.

Let a be an integer greater than or equal to 1 and b be a real number greater than 1. Let c be a positive real number and d a nonnegative real number. Given a recurrence of the form

• T (n) = a T(n/b) + n^c .. if n > 1

• T(n) = d .. if n = 1

then for n a power of b,

1. if log_b a < c, T (n) = Θ(n^c),
2. if log_b a = c, T (n) = Θ(n^c log n),
3. if log_b a > c, T (n) = Θ(n^{log_b a}).

1) T(n) = 2T(n/2) + 0(1)

In this case

a = b = 2;
log_b a = 1; c = 0 (since n^c =1 => c= 0)

So Case (3) is applicable. So T(n) = Θ(n) :)

---

2) T(n) = T(sqrt(n)) + 0(1)

Let m = log₂ n;

=> T(2^m) = T( 2^{m / 2} ) + 0(1)

Now renaming K(m) = T(2^m) => K(m) = K(m/2) + 0(1)

Apply Case (2).

---