Register

time complexity

• edited by
1,332 views
2 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 __________.

1 Answer

Voting & Accepting an answer helps improve the community
← Previous · LR(1) parser and LR(...Next → · SQL and relational a...
← Previous in category · doubtNext in category → · max heap
Position:
Show:

Related questions

1 1 vote
0 0 answers
2.2k
2.2k views
syncronizing asked Mar 15, 2019
2,219 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)*algorit...
1 1 vote
1 1 answer
1.7k
1.7k views
VikramRB asked Jan 20, 2019
1,712 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)$
0 0 votes
2 2 answers
1.4k
1.4k views
Nidhi Budhraja asked Nov 29, 2018
1,419 views
Ace Test Series: Algorithms - Time Complexity
What is the time complexity of T(n) = T(n/3) + T(n/9) +n?
1 1 vote
1 1 answer
6.2k
6.2k views
gmrishikumar asked Nov 22, 2018
6,188 views
How is the time Complexity of this problem O(n log log n)?
int A(int n){ for(i = 1; i < n; i++) for(j = 1; j < i; j *= 2) for(k = j; k >= 1; k /= 2) if(n = 0) return 1; else...