The Gateway to Computer Science Excellence

+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 ...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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,292 answers

198,234 comments

104,917 users