1 vote

I was wondering whether the recurrence **T(n) = T(n/2) + 2 ^{n} **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.

0

I have completely copied this portion from wikipedia

https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms) .

1.

2.

3.

4. https://gateoverflow.in/25346/can-these-be-solved-by-masters-theorem

5. https://gateoverflow.in/10619/recurrence

6. https://gateoverflow.in/231153/masters-theorem

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)

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

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

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 vote

Check this solution

https://math.stackexchange.com/questions/280080/solving-recurrence-tn-2-tn-2-2n

0 votes

0 votes

**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

Ok so for the given function **T(n) = T(n/2) + 2^n**

for 2^n lets take its strict lower bound (nlogn)

So the function becomes **T(n) = T(n/2) + nlogn **and by masters theorem its time complexity comes out 0(nlogn)

Now lets take upper bound of 2^n i.e. 0(n^n)

so function becomes T(n) = T(n/2) + n^n and by masters theorem its time complexity becomes 0(n^n)

Thus we can conclude that whenever the function is changed to its strictly lower or upper bound , the time complexity becomes equals to that function. Hence for the function **T(n) = T(n/2) + 2^n** the time complexity equals 0(2^n)