GATE CSE 2015 | Set 2 | Question: 17

Question

Consider a complete binary tree where the left and right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

• A. $\Omega(\log n)$
• B. $\Omega(n)$
• C. $\Omega(n \log n)$
• D. $\Omega(n^2)$

Comments

so why log(n)
why not O(1)

---

Worst case the root element have to be swapped down to one the leafs when 'heapify' is applied on root. So it is log n.

---

Similar question: https://gateoverflow.in/3616/gate-it-2006-question-72

Answer 1

Answer is (A).

Here, lower bound imply best algorithm which works for all cases and hence we should consider worst-case.

Max-Heapify(root).

Comments

@Pranavpurkar isn' t the time for heapify at a node O(logn) or am I missing something?

---

is it right to say that in worst case starting from root till logn level (as it is complete binary tree) at each level in worst case root element will go through 2 comparison and 1 swap so total 2logn comparisons and logn swaps = 3logn = O(logn)

please correct if anything wrong

---

basically heapify the root of CBT : omega(logn)

Answer 2

now to make it max heap it take only 2 swap and 4 comparision which is nothing but its height.

Let's level of root node is 0.

Swap: in the worst case, on every level from level-1 ::: 1 swap.

Comparission : in the worst case, on every level, 1 comparission between siblings, 1 comparission with the node from upper level.

As, height of the tree is log n, at every level constant amount of work, so $\log n$ time needed.

Option A is answer.

Comments

upper bound O(n)?

---

@J.Komal  it will be O(logn), as root may need to be heapifiy till down to a leaf, and a complete binary tree of size n has height logn, so in worst case the root element traverse logn height.

---

worst will be log n only

Answer 3

Go ahead guys with next question without wasting your time. It's a poorly formed question. If this question repeats anywhere you will be able to answer Ω(log n) as it is the smallest. If this question repeats with Ω(1) in option then choose Ω(1) only.

Best Case $\rightarrow$ Ω(1)

Worst Case $\rightarrow$ O(log n)

Comments

Nope it's not a poorly framed question. Best case given by you is just free from all constraints. Any problem in this world can be solved in constant time if the problem is already solved.

Consider this, you have an array of say some million numbers now you ask the lower bound for sorting the array with any comparison based algorithm. What you will say? According to you the best case would be omega 1, because you know the range of numbers, you know that if you write numbers in increasing order without even looking at the jumbled up sequence you will get a sorted order. But why then this will be a problem if you never gonna look at the problem. Infact why could be any problem in this universe exits if they are already solved?

Similarly here,

The root as the 2nd largest element is the value desired by you because maybe you want the problem to never exist but no it should exist and it should have some measurable running time bounds upon which we can work and improve the algorithms and it should also have a lower bound upon which we can say that the given problem should and must take more time then a particular given time.

---

I totally understand your point, but at the end of the day the question asks for the lower bound which simply put aks for a function f(x) on the number line which for which no matter the problem ( heap structure), our function should be the lower bounder of the problem function, and since the problem could very well be solved by O(1) shouldn't our lower bound also be omega of (1)?

Answer 4

As to APPLY Heapify(node) to any node its lhs and rhs subtrees must  have to be  HEAP.

Lower bound for heap is its HEIGHT given by log(n)

so it's answer must be A

Answer 5

🧠 Heapify from Root: What’s the Cost?

• The tree is complete, so its height is log⁡n.

• Heapifying the root involves:

  • Comparing it with its children.

  • Possibly swapping with the larger child.

  • Repeating this down the path until the heap property is restored.

So in the worst case, the root travels all the way to a leaf → Θ(log n) operations.

Answer 6

Here we take the lower bound for the problem.

This is found by the worst case complexity of the best algorithm.

For Example: For sorting problem the lower bound is nlogn -> this means for the worst case the complexity of a sorting algorithm can't be lower than nlogn and is always higher than nlogn (best algorithm say merge sort in terms of time complexity) -> Omega(nlogn).  

Now, The Worst case Complexity of max-heapify is O(logn). So for all cases this is the lowest possible lower bound.

Therefore Option A is right.