Can we solve the recurrence T(n) = T(n/2) + 2^n by masters theorem, if possible?
in Algorithms
10,275 views
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
10.3k views

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 ...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)
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...
0
0
1 vote
1 vote
1 vote
1 vote

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

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

1 comment

This is not a polynomial function but an exponential function.
0
0

Related questions

0 votes
0 votes
1 answer
4