Can we solve the recurrence T(n) = T(n/2) + 2^n by masters theorem, if possible?
in Algorithms
1 vote
1 vote

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.

in Algorithms

Subscribe to GO Classes for GATE CSE 2022

6 Answers

2 votes
2 votes
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 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)
1 vote
1 vote
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 by
How j is 1???? Pls clear.. log1 is 0.. and a=1 here... Pls clear...
1 vote
1 vote
1 vote
1 vote

Note: This answer is copied directly from Quora, here’s the link:-

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$




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)


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

0 votes
0 votes
master theorem provide wrong solution for polynomial function

1 comment

This is not a polynomial function but an exponential function.

Related questions

0 votes
0 votes
1 answer