Register

#algo

• retagged by
472 views

1 Answer

Best answer
6 votes
6 votes

T(n)=4T(n0.5) +(logn)2
put n=2k
T(2k)=4T(2k/2) +(k)2
make T(2k)=s(k)
s(k)=4s(k/2) +(k)2     use master thm 2nd case
klogba=klog24 =k2  
tc=theta(k2 logk) put k=logn
tc=theta((logn)2.loglogn)

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

Related questions

913
views
1 answers
0 votes
pradeepchaudhary asked May 9, 2019
913 views
analysis of algorithm
User Avatar
1.7k
views
1 answers
1 votes
Rajesh Pradhan asked Oct 14, 2016
1,688 views
#Algo
On which of the following recurrence relation Master Theorem cannot be applied?A. T(n)=2T(n/2)+nlognB. T(n)=T(n/2)+1C. T(n)=8T(n/2)+lognD. T(n)=7T(n/4)+n2I think we can apply on all. But plz correct me with reason.Thanks
User Avatar
551
views
1 answers
3 votes
papesh asked Oct 12, 2016
551 views
#algo
$T(N) = T(N/4) + T(N/2) + N^{2}$Find Order of given Reccurence??
User Avatar
3.6k
views
1 answers
0 votes
Sumit Singh Chauhan asked Aug 18, 2018
3,647 views
Geeks - Doubt
What is time complexity of fun()?int fun(int n){ int count = 0; for (int i = n; i > 0; i /= 2) for (int j = 0; j < i; j++) count += 1; return count;}(A) O(n^2)(B) O(nLogn)(C) O(n)(D) O(nLognLogn)
User Avatar
Link Copied!