Register

time complexity

• edited by
608 views
2 votes
2 votes

Consider the description to solve for any problem ‘S’ using recursive tree method S1  below:

S1 : Recursion depth of tree is atmost log$_2$ n.
S2 : Total number of nodes at level i is atmost 5$^i$.
S3 : The maximum number of leaves is atmost 5$^{log_2n}$.
S4 : The recurrence is bounded by summation.
Using all four statement if T(n) represents the time complexity to solve problem ‘S’ and gives T(n) = O(n$^p$).
Then the value of p is __________.

• edited by
User Avatar

1 Answer

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
0 answers
1
syncronizing asked Mar 15, 2019
1,298 views
Time complexity
Is this the correct way to solve ? Q) int algorithm(int n) { int sum =0;k,j; for (k=0;k<n/2;k++) for(j=0;j<10;j++) sum++; return 4*algorithm(n/2)*algorithm(n/2)+algorithm(n/2)*algorithm(n/2) }
Is this the correct way to solve ?Q) int algorithm(int n){ int sum =0;k,j; for (k=0;k<n/2;k++) for(j=0;j<10;j++) sum++; return 4*algorithm(n/2)*algorit...
User Avatar
1 votes
1 votes
1 answer
2
VikramRB asked Jan 20, 2019
1,042 views
Recurrence relation and Time Complexity
What is the time complexity of the following recurrence relation and step to derive the same $T(n) = T(\sqrt{n}) + log(logn)$
What is the time complexity of the following recurrence relation and step to derive the same$T(n) = T(\sqrt{n}) + log(logn)$
User Avatar
0 votes
0 votes
2 answers
3
Nidhi Budhraja asked Nov 29, 2018
693 views
Ace Test Series: Algorithms - Time Complexity
What is the time complexity of T(n) = T(n/3) + T(n/9) +n?
What is the time complexity of T(n) = T(n/3) + T(n/9) +n?
User Avatar
Link Copied!