retagged by
428 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
Answer:

Related questions

0 votes
0 votes
1 answer
1
1 votes
1 votes
1 answer
2
Rajesh Pradhan asked Oct 14, 2016
1,610 views
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 a...
3 votes
3 votes
1 answer
3
papesh asked Oct 12, 2016
469 views
$T(N) = T(N/4) + T(N/2) + N^{2}$Find Order of given Reccurence??
0 votes
0 votes
1 answer
4
Sumit Singh Chauhan asked Aug 18, 2018
3,399 views
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^...