The Gateway to Computer Science Excellence
0 votes

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 by (387 points) | 706 views

4 Answers

+1 vote
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)
by (287 points)
+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
by (37 points)
How j is 1???? Pls clear.. log1 is 0.. and a=1 here... Pls clear...
+1 vote
by Active (1.1k points)
0 votes
master theorem provide wrong solution for polynomial function
by (93 points)
This is not a polynomial function but an exponential function.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,917 users