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

yes.this point is discussed below

---

Catch here is we have a complete binary tree

So this means, this already satisfies the almost complete binary tree property of a max heap

now it is asking best case

$\Omega(logn)$ as this the height of the tree

suppose i have a binary tree

 like

               1

100                    2

To convert this into Max heap, just 1 swap is required.

hence log(n)

---

Sucha good question @GO Classes

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

I have a query here if the top most element is the maximum element then it will be Heap by default so O(1) complexity. In the question it is mentioned to convert Binary tree into Heap but it is not mentioned Max Heap or Min Heap
Correct me if I am wrong

---

It is not mentioned - so we can do either and natural choice should be Max Heap. But what is the significance of root being the max element- that gives the best case. But we have to see for all cases- the best time complexity for the worst case input.

---

what would be the time complexity if the tree will be like this ?

---

@arjun sir, if we are doing only two comparisons if we have the best case that is input is the maximum element among all..then why tc is log n?

---

It is not just 2 comparisons. We might have to traverse down the whole height of the tree- it is exactly the Max-Heapify procedure given in Cormen or any algorithm text for Heap Sort.

---

Sir,but they are saying both the subtrees are max heaps..and root of max heap is largest element..so what is the need to traverse down(correct me if i m wrong kindly)..can u elaborate..

---

you can see 3 comments before- a figure is given. How can we make that tree a heap in 2 comparisons?

---

Given figure dont have best case..if we had 25 as a root it would be the best case..what i m saying is maxheapify root has tc log n is of course correct! But here in the question they are already providing left and right subtrees as max heap and asking for lower bound i.e. best case we can consider..the maxheapify proc is for the normal tree to heap conversion..and that tree dont have such benefits.

---

@​nilamd, $\Omega (1)$ is not in options, so we shud go for   $\Omega (log \ n)$.

@Arjun Sir, Question asks for, lower bound for the number of operations , so, I think $\Omega (1)$ shud be right answer(but not in options, so, we can go for $\Omega (log\ n)$).

---

@amar sir..thanx for conclusion..finally

---

@Amsar Then lower bound on the no. of comparisons required to sort n numbers is ?

---

$\Omega(n)$  -  as even if array is sorted then also algo will execute , insertion sort can give least comparisons.

---

This is not a complete binary Tree, but according to the question the given Tree is a complete binary Tree and left, right subtrees of Root is heap as well.Root may have any value, hence if we call Max-heapify at Root node then resultant Tree will be a Heap and it will take O(log n) time.

---

@Arjun sir,

If there is one more option say E,which says:-

 

Ω(1), then will the answer remains same or changes to E?

---

@rahul, having the same doubt.

@Arjun sir, your statement confusing me a lot.

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

if we consider worst case in lower bound..then what is the use of upper bound ??

isnt lower bound is synonoums to "best case input complexity"

---

---

@reena Need to get a good reference. But from what I have seen lower bound is for best case input if "an algorithm is given". Otherwise it assumes the best algorithm and worst case input.

---

yes sir, you are correct about lower bound of a Problem. REF

sir, can you confirm the following statement.I think it best describe the confusion between lower bound of a Problem and Lower bound of a particular Algorithm.

---

Whatever the bound (upper or lower), we are always talking about the worst-case input that we can consider. For example, in sorting, we assume that the worst-case is an unsorted input list.

My understanding is that problems have a lower bound. For example, we say that the lower bound of comparison-based sorting is $\Omega (nlogn)$; we are making no assumptions about what particular comparison-based sorting algorithm we use. Whatever the algorithm (merge sort, quick sort, etc), we cannot do better than this bound of $\Omega(n log n)$. Lower bounds tell us, intuitively, how hard a particular problem is.

When we talk about a specific algorithm, then we talk about upper bounds. For example, we say that the upper bound of bubble sort is $O(n^2)$ and the upper bound of merge sort is $O(n log n)$. Upper bounds, intuitively, tell us how good a particular algorithm is at solving the problem

---

---

@reena Pretty good :) You are far ahead compared to last year.

Lower bound in turn does exactly that -- it tells how hard a problem is. Upper bound is usually given for an algorithm and once the upper bound and lower bound becomes the same => we have found the best algorithm (at least asymptotically) for the given problem.

---

thank you so much sir :)

---

@priyavssut We have to consider a complete binary tree whose left and right are max heaps, right? This example is not complete binary tree.

---

So in simple words we can say for an algorithm => we search for upper bound of that algorithm

but for a Problem => we search for worst input on best algorithm isn't it ?

---

@Arjun Sir, the statement you said:

"Lower bound in turn does exactly that -- it tells how hard a problem is. Upper bound is usually given for an algorithm and once the upper bound and lower bound becomes the same => we have found the best algorithm (at least asymptotically) for the given problem."

It implies that in all the sorting algorithms, merge sort is best one.

And also, there can never be any algorithm(in future) which will be better than merge sort.

But this could be wrong.

---

here, we are given with a tree whose right and left subtree’s are already max heap and this tree is a CBT . so suppose we have the second maximum element at the root ,in this case only constant time is needed to make the tree as a maxheap but if we have the smallest element at the root then we have to do the heapify procedure from top to the leaf. and this will take O(n) right? so if we consider the second case then the time required will be Ω(n)? 

please help in this!

---

Thanks @reena_kandari mam, such a beautiful insight you have given. Problems have various solutions and it’s lower bound tell us the most optimal algorithm in present or future can not do better than this. Where as upper bounds on algorithms tell us how close our solution is to the optimal one.

---

We can think of the question like , we earlier had a max heap . Then we did deleteMax that is we deleted the maximum element . So the right most element from the leaf level came up to take its place . Now we need to again maintain the maxheap property .

Answer 2

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

so logn time needed.

A is asswer

Comments

@Arjun sir if lower bound is worst case input of best algorithm,then what about UPPER BOUND.

isn't lower  bound=best case complexity?

and upper bound=worst case complexity.?

---

@Prashant.

Sir i think here it will take total 4 comparisons and 2 swaps! 

how with only 2 comparisons and 2 swaps we can make this max heap?  as we have to again compare 10 with its respective child nodes!

please help in this!

---

Condition to construct heap is it must be complete binary tree(From left to right)

Answer 3

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 4

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)