Register

Time Complexity of Max_heapify(A,i) (CLR 3rd edition Page no. 155)

308 views
1 votes
1 votes

The running time of MAX_HEAPIFY on a subtree of size n rooted at a given node i is the Thete(1) time to fix up the relationships among the element A[i] , A[LEFT(i)] and A[RIGHT(i)] , plus the time to run the MAX_HEAPIFY on subtree rooted at one of the children of node i  .

The children's subtree each have size at most (2n/3) - the worst case occurs when the level of the tree is exactly half full and therefore we can describe the running time of MAX_HEAPIFY by the recurrence -

T(n) <= T(2n/3) + theta(1)

Could anyone explain the bold lines in detail ?

User Avatar

Please log in or register to answer this question.

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

Related questions

2 votes
2 votes
0 answers
1
dragonball asked Nov 10, 2017
207 views
Worst case running time of MAX_HEAPIFY
Show that the worst case time complexity of MAX_HEAPIFY is Ω(logn ) .
Show that the worst case time complexity of MAX_HEAPIFY is Ω(logn ) .
User Avatar
2 votes
2 votes
1 answer
2
dragonball asked Oct 21, 2017
1,150 views
CLR 3rd Edition page no. 42 Q.n. c
Wha is the relationship between the running time of insertion sort and the number of inversions in the input array ? Is the circled text should be greater instead of less .Plz justify . PS: This image has been taken from solun manual of CLR.
Wha is the relationship between the running time of insertion sort and the number of inversions in the input array ?Is the circled text should be greater instead of less ...
User Avatar
0 votes
0 votes
0 answers
3
dragonball asked Jun 22, 2017
637 views
CLR 3rd edition , Page no. 49 , second para
"The running time of insertion sort is not Ω($n^{2}$) , since there exists an input for which insertion sort runs in $\Theta (n)$. It is not contradictory , however , to say that the worst case running time of insertion sort is Ω($n^{2}$) " . Could anyone explain this line ?
"The running time of insertion sort is not Ω($n^{2}$) , since there exists an input for which insertion sort runs in $\Theta (n)$. It is not contradictory , however , t...
User Avatar
0 votes
0 votes
1 answer
4
dragonball asked Jun 22, 2017
381 views
CLR 3rd edition , page no 87, Q.no. 4.3-6
While solving this recurrence T(n) = 2T(n/2 + 17) + n what is the need of 17 and how to go forward to solve this question using the method of master theorem ?
While solving this recurrence T(n) = 2T(n/2 + 17) + n what is the need of 17 and how to go forward to solve this question using the method of master theorem ?
User Avatar
Link Copied!