GATE Overflow Test Series | Algorithms | Test 1 | Question: 24

Question

Which of the following statements is/are TRUE? (Mark all the appropriate choices)

• A. The worst case runtime for searching in a binary tree can be $\Omega (n).$
• B. The minimum number of comparisons to sort $5$ elements is $4.$
• C. There can be at most $\left \lfloor \dfrac{n}{2^{h-1}} \right  \rfloor $ nodes of height $h$ ($h$ starting from $1$) in any $n$ element heap.
• D. The time to find the maximal element in a min-heap of $2^n-1$ elements is $\Omega(2^n).$

Answer 1

A is TRUE. Happens for a left-skewed or right-skewed binary tree.
 
 B is FALSE. Minimum number of comparisons to sort $5$ elements is $7$ as proved by  Demuth in his Ph.D. thesis. https://cs.stackexchange.com/questions/44981/least-number-of-comparisons-needed-to-sort-order-5-elements
 
 C is FALSE. There can be at most $\left \lceil \dfrac{n}{2^{h-1}} \right \rceil $ nodes of height $h$ in any $n$ element heap when $h$ starts from $1$ and this changes to $\left \lceil \dfrac{n}{2^{h+1}} \right \rceil $ when $h$ starts from $0$. Ref: https://www2.cs.sfu.ca/CourseCentral/307/petra/2009/SLN_2.pdf
 
 D is TRUE as maximum element in a min-heap will be at the last level and it can be any one of the possible $n/2$ elements in the last level.

Comments

oh, actually there was a typo in the question which came from an edit- it was supposed to be floor and not ceil. The given option C statement was indeed correct. See the answer now.

---

@gatecse @Arjun sir, the last options is FALSE,

as there are 2^n – 1 elements in heap, we will have 2^(n/2) element in the last level.

2^(n/2) is not omega(2^n)

 there are 2^(n-1) element in last level.

so, it is omega(2^n)

---

is there any difference between maximal and maximum element here?