search
Log In
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
0 votes
24 views

Help me solve these three questions on Master’s Theorem: 

  1. T(n) = T(n/2) + 2^n 
  1. T(n) = 2T (n/2) + n/logn 
  1. T(n) = 16T (n/4) + n! 
in Algorithms 5 points 24 views

1 Answer

0 votes

@Naman9495

 

Follow Extended Masters Theorem Below.

Using Extended Masters Theorem T(n)=2T(n/2)+n/logn can be solved easily as follows….

Here n/log n part can be rewritten as n * (logn)^-1,

Effictively maaking value of p=-1.

Now Extended Masters Theorem can be applied easily,

it will relate to case 2b of Extended Masters Theorem .

T(n)= O(nloglogn)....

 

https://www.youtube.com/watch?v=1K9ebQJosvo  

 

https://www.youtube.com/watch?v=XcZw01FuH18  

 

https://www.youtube.com/watch?v=IawM82BQ4II  

 

https://www.csd.uwo.ca/~mmorenom/CS424/Ressources/master.pdf 

633 points
...