10,275 views

I was wondering whether the recurrence T(n) = T(n/2) + 2n could be solved by using master theorem, and what would be the way. I tried solving the recurrence but can't. There is no mention to it in CLRS book. Please help. Thanks in advance.

### Subscribe to GO Classes for GATE CSE 2022

We can try to solve it in this way

Lets consider T(n)=a*T(n/b) + Theta( pow(n,k) *log^p n)

Now T(n)=T(n/2) + pow(2,n)

therefore a=1 b=2 n=2 k=n and p=0

compare a and pow(b,k) i.e 1 and 2^n ...so if n=1,2,... then a < pow(b,k) and p=0

then the T(n) becomes T(n)=Q(pow(n,k)*log^p n

again by substituting p=0 we have T(n)=Q(pow(n,k)

then by substitutuing n and k values we have n=2 k=n

therefore T(n)=pow(2,n)
Masters theorem if of form

T(n) = aT(n/b) + f(n)

there will be 3 cases:

J = n^(LOGb(a))  // b is base , it is n to the power of log base b

1. f(n) = J => T(n) = J * logn

2. f(n) <polynomial J // f(n) is polynomial lesser than J

=> T(n) = J

3. f(n) > polynomial J // f(n) is polynomial greter than J

=> T(n) = f(n)

for given qustion J = 1 and f(n) is 2^n

2^n is polynomialy bigger than J hence T(n) = 2^n

### 1 comment

edited
How j is 1???? Pls clear.. log1 is 0.. and a=1 here... Pls clear...
by

Note: This answer is copied directly from Quora, here’s the link:- https://www.quora.com/How-do-you-solve-T-n-T-n-2-2-n-through-the-master-theorem

I am going to assume a base case when T(1) occurs, where it is some constant. You can indeed use the Master Theorem here (I am referring to the one in CLRS). As this is a great example for me to hand-wave as an exercise, I will not provide a full solution here; only the end-result and a tip on how to get it.

I am going to assume the following form when using the Master Theorem:

T(n)=aT(n/b)+f(n), where a≥1 and b>1 are constants and f(n) is an asymptotically positive function.

You can use the following case of the Master Theorem…

In short, you’re going to end up with $T(n)∈Θ(2^n).$

Aside: Instead, I’m going to show you another way to do this, without the Master Theorem. For simplicity, I am going to assume that nn is a power of 2 (you do not need to do this). I’m just going to use repeated substitution.

$T(n)=T(n/2)+2^n$

$=(T(n/4)+2^{n/2})+2^n$

$=(T(n/8)+2^{n/4})+2^{n/2}+2^n$

$=(T(n/16)+2^{n/8})+2^{n/4}+2^{n/2}+2n$

Well if you are observant, you will notice if we continue this, I can just put in powers of two in above. Then…

$T(n)=T(n/2^i)+2^{n/2^{i-1}}+2^{n/2^{i-1}}+ ...+2^{n/2^{1}}+2^{n/2^{0}}.$

Well, we need when $n/2^i=1$, so just re-arrange this and apply logarithms to both sides and we obtain that

$i=\log_{2}n$

I am going to assume we keep substituting until we get T(1), then use a simple bound (that is a finite geometric series) that will consist of at least the terms of the sum.

=T(1)+$\sum_{j=0}^{i} 2^{n/2^j}$

<T(1)+$\sum_{j=0}^{i} 2^{j}$

=T(1)+$2^{n+1}−1$ (Applying the fact it is a finite geometric series with r=2)

=T(1)+$2(2^n)−1$

Well, we said T(1) is constant, so T(1)−1 must also be constant.

We can see that $2(2^n)∈Θ(2^n), therefore, T(n)∈Θ(2^n).$

master theorem provide wrong solution for polynomial function

### 1 comment

This is not a polynomial function but an exponential function.