The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
55 views

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 ?

asked in Algorithms by Active (2.1k points) | 55 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
48,756 questions
52,850 answers
183,548 comments
68,743 users