Register

Master theorem

• retagged by
738 views

1 Answer

Best answer
2 votes
2 votes

here a=2  b=2 nlogba=n
f(n)=nlogn
now f(n)/nlogba=logn 
acc 2 basic master thm f(n) must b polynomial time smaller/greater than  nlogba
but here it is greater by logn time so master thm not applied here

----but u  can use extended master thm ie.

acc 2 this ans=theta(nlog2n)

• edited by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
dragonball asked Oct 15, 2017
525 views
Master Theorem
User Avatar
0 votes
0 votes
2 answers
2
rahul sharma 5 asked Dec 14, 2016
489 views
Master Theorem Algorithm
How is master theorem applicable here?
How is master theorem applicable here?
User Avatar
1 votes
1 votes
1 answer
3
mdboi asked Oct 28, 2022
748 views
𝑇(𝑛)=16𝑇(𝑛/4)+5𝑛^3 using the master theorem
how do i apply master theorem to this? 𝑇(𝑛)=16𝑇(𝑛/4)+5𝑛^3
how do i apply master theorem to this? 𝑇(𝑛)=16𝑇(𝑛/4)+5𝑛^3
User Avatar
2 votes
2 votes
1 answer
4
iarnav asked Jan 11, 2018
1,111 views
recurrence using Master theorem
can we solve this T(n) = T(n/2) + 1 using master theorem?
can we solve this T(n) = T(n/2) + 1 using master theorem?
User Avatar
Link Copied!