Solving recurrence T(n) = 2T(n/2) + Θ(1) by substitution

Question

So I am pretty sure it is O(n) (but it might not be?), but how do you solve it with substitution?

If you assume T(n) <= c * n, what is the induction steps?

Permeance

Tell us why you think it is O(n) – Halflength

Actually, maybe it have to be bigger? Because if you substitute for O(n), you end up with T(n) <= cn + d. And d has to be positive for it can't be. Maybe it's n^2 – Permeance

Try to tackle two slightly easier problems: T(n) = 2 * T(n/2), and T(n) = T(n/2) + O(1). Which of these problems is most like yours? Can you apply the results to your problem? – Pug

Answer 1

First of all,I'd like to assume clearly that Θ(1)=k,some constant.

Next,proceeding using substitution method, we get

 T(n)=2T(n/2)+Θ(1)
     =2T(n/2)+k
     =2{2T(n/4)+k)+k
     =4T(n/4)+3k
     =...
     =n.T(1)+(n-1)k
     =n.k+(n-1)k
     =2nk-k
     =O(n).

If you assume it as T(n) <= c * n,you should start with T(1) and assume for T(n) to be correct,and then proceed to show that it is correct for T(n+1) by using the assumption for T(n).

BTW,your assumption was right!

Stedman

After the 5th line, the generalization should be 2^m T(n/2^m) + (2^m - 1)k. Now to make T(1), we let 2^m = n which gives us the 6th line. – Rang

Answer 2

For simplicity, let's assume that the O(1) term hides some constant c, so the recurrence is really

T(n) = 2T(n/2) + c

Let's also assume for simplicity that T(1) = c.

You're venturing a (correct) guess that

T(n) <= an + b

For some constants a and b. Let's try to prove this inductively.

For n = 1, we need a and b to be such that

c <= a + b

For the inductive step, we want

T(n) <= 2T(n/2) + c

Substituting our guess gives

T(n) <= 2(an / 2 + b) + c

= an + 2b + c

Notice that if 2b + c = b, the left-hand side of this expression would be an + b, the upper bound we need. Thus we need to choose a and b such that

c <= a + b

2b + c = c

One possible choice that works here is a = 2c and b = -c, giving that T(n) <= 2cn - c = O(n).

Hope this helps!

Delilahdelimit

Answer 3

Master's theorem is a good fit for this problem :

Comparing the given equation

T(n) = 2T(n/2) + c

with the formulae

T(n) = aT(n / b) + (n^k log^p n)
where a >= 1, b > 1, k >= 0 and p is real

we can say it satisfies the condition a > b^k since a = 2, b = 2 and k = 0
so, T(n) = θ(n^{log _b a}) = θ(n)

Walters