Register

Time complexity

• retagged by
811 views

2 Answers

Best answer
1 votes
1 votes

Here master theorem is fail. Becz ration of f(n) and n^logba is logn . So we can apply extended master theorem.

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

Related questions

7 votes
7 votes
3 answers
1
bts asked May 29, 2018
1,879 views
Time complexity , Recursion
Why is recursive equation of following code $T(n)=T(n/2)+O(1)$, not $T(n)=8*T(n/2)+O(1)$? int x=0; int A(n) { if(n==1) return 1; else { X+=8A(n/2)+n^3; } return X; }
Why is recursive equation of following code $T(n)=T(n/2)+O(1)$, not $T(n)=8*T(n/2)+O(1)$? int x=0; int A(n) { if(n==1) return 1; else { X+=8A(n/2)+n^3; } return X; }
User Avatar
3 votes
3 votes
1 answer
2
Ashish Sharma 3 asked Jun 16, 2017
1,778 views
Time Complexity for Recurrence relation
What will be the time complexity for the following recurrence relation? $T(n) = 8\sqrt{n} T(\sqrt{n})+(log n)^{2}$ According to me it is $\Theta (n(logn)^{3})$ . Please confirm.
What will be the time complexity for the following recurrence relation?$T(n) = 8\sqrt{n} T(\sqrt{n})+(log n)^{2}$According to me it is $\Theta (n(logn)^{3})$ . Please con...
User Avatar
2 votes
2 votes
1 answer
3
reena_kandari asked Jan 10, 2017
375 views
Time complexity
User Avatar
0 votes
0 votes
3 answers
4
Anmol Verma asked Jan 9, 2017
1,494 views
time complexity Master's Theorem problem from CLRS
1) T(n)=T(n-1)+1/n. 2) T(n)=T(n-1) +1/log(n) 3)T(n)=3T((n/3) - 2)+n/2. 4)T(n)=T(n/2)+T(n/4)+T(n/8)+n. Use Masters theorem
1) T(n)=T(n-1)+1/n.2) T(n)=T(n-1) +1/log(n)3)T(n)=3T((n/3) - 2)+n/2.4)T(n)=T(n/2)+T(n/4)+T(n/8)+n.Use Masters theorem
User Avatar
Link Copied!