Can some one help solving this recurrence relation?

Question

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

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

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

Can some one help? T

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).

---

Answer 2

Let's look at the first recurrence, T(n) = 2T(n/2) + 1. The n/2 is our clue here: each nested term's parameter is half that of its parent. Therefore, if we start with n = 2^k then we will have k terms in our expansion, each adding 1 to the total, before we hit our base case, T(0). Hence, assuming T(0) = 1, we can say T(2^k) = k + 1. Now, since n = 2^k we must have k = log_2(n). Therefore T(n) = log_2(n) + 1.

We can apply the same trick to your second recurrence, T(n) = T(n^0.5) + 1. If we start with n = 2^2^k we will have k terms in our expansion, each adding 1 to the total. Assuming T(0) = 1, we must have T(2^2^k) = k + 1. Since n = 2^2^k we must have k = log_2(log_2(n)), hence T(n) = log_2(log_2(n)) + 1.

Answer 3

For part 1, you can use Master Theorem as @Prasoon Saurav suggested.

For part 2, just expand the recurrence:

T(n) = T(n ^ 1/2) + O(1)         // sqrt(n) = n ^ 1/2
     = T(n ^ 1/4) + O(1) + O(1)  // sqrt(sqrt(n)) = n ^ 1/4
     etc.

The series will continue to k terms until n ^ 1/(2^k) <= 1, i.e. 2^k = log n or k = log log n. That gives T(n) = k * O(1) = O(log log n).

Answer 4

Let's look at the first one. First of all, you need to know T(base case). You mentioned that it's a constant, but when you do the problem it's important that you write it down. Usually it's something like T(1) = 1. I'll use that, but you can generalize to whatever it is.

Next, find out how many times you recur (that is, the height of the recursion tree). n is your problem size, so how many times can we repeatedly divide n by 2? Mathematically speaking, what's i when n/(2^i) = 1? Figure it out, hold onto it for later.

Next, do a few substitutions, until you start to notice a pattern.

T(n) = 2(2(2T(n/2*2*2) + θ(1)) + θ(1)) + θ(1)

Ok, the pattern is that we multiply T() by 2 a bunch of times, and divide n by 2 a bunch of times. How many times? i times.

T(n) = (2^i)*T(n/(2^i)) + ...

For the big-θ terms at the end, we use a cute trick. Look above where we have a few substitutions, and ignore the T() part. We want the sum of the θ terms. Notice that they add up to (1 + 2 + 4 + ... + 2^i) * θ(1). Can you find a closed form for 1 + 2 + 4 + ... + 2^i? I'll give you that one; it's (2^i - 1). It's a good one to just memorize, but here's how you'd figure it out.

Anyway, all in all we get

T(n) = (2^i) * T(n/(2^i)) + (2^i - 1) * θ(1)

If you solved for i earlier, then you know that i = log_2(n). Plug that in, do some algebra, and you get down to

T(n) = n*T(1) + (n - 1)*θ(1). T(1) = 1. So T(n) = n + (n - 1)*θ(1). Which is n times a constant, plus a constant, plus n. We drop lower order terms and constants, so it's θ(n).

Prasoon Saurav is right about using the master method, but it's important that you know what the recurrence relation is saying. The things to ask are, how much work do I do at each step, and what is the number of steps for an input of size n?

Answer 5

Recurrence relations and recursive functions as well should be solved by starting at f(1). In case 1, T(1) = 1; T(2) = 3; T(4) = 7; T(8) = 15; It's clear that T(n) = 2 * n -1, which in O notation is O(n).
In second case T(1) = 1; T(2) = 2; T(4) = 3; T(16) = 4; T(256) = 5; T(256 * 256) =6; It will take little time to find out that T(n) = log(log(n)) + 1 where log is in base 2. Clearly this is O(log(log(n)) relation.