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

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 (1.7k points) | 59 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
49,783 questions
54,511 answers
75,109 users