# Algorithms Self Doubt. Topic- Sorting and Max-Heap

49 views

Which of the following is/are true? [MSQ]

1. If f(n) = Ο(g(n)) and g(n) = Ο(h(n)), then h(n) = Ω( f(n))
1.  If f(n) = Ο(g(n)) and g(n) = Ο( f(n)) then f(n) = θ(g(n))
2. The sequence < 20, 15, 18, 7, 9, 5, 12, 3, 6, 2 > is a max-heap.
3. Suppose that instead of using Build-Heap to build a max-heap in place, the Insert operation is used n times. Starting with an empty heap, for each element, use Insert to insert it into the heap. After each insertion, the heap still has the max-heap property, so after n Insert operations, it is a max-heap on the n elements. Then this heap construction runs in Ο(n logn) time.

1 vote
Finally I figured out the correct explanation for option (D).

since it is told that the max heap will be constructed by using the insert(insert to the leaf node and then heapify) operation “n” times. Hence, the first key is inserted as no need to heapify with one node therefore no operation, now second key inserted then there are two keys and then we will apply heapify on the second key T.C. O(log n) i.e log 2 (since two keys). Now in this way if we proceed.
The total time complexity will be: "log 2 + log 3 + ….. + log n” which is Summation of log n (n from 2 to n) equates to O(n logn).

A,B,C options are easy and the solution is provided by other user you can refer to that.
17 points
0

## https://gateoverflow.in/459/gate-cse-2008-question-47

The total time complexity will be: "log 2 + log 3 + ….. + log n” which is Summation of log n (n from 2 to n) equates to O(n logn).

633 points

## A) If f(n) = Ο(g(n)) and g(n) = Ο(h(n)), then h(n) = Ω( f(n))

https://gateoverflow.in/249318/asymptotic-notations

## True ...

### D) Suppose that instead of using Build-Heap to build a max-heap in place, the Insert operation is used n times. Starting with an empty heap, for each element, use Insert to insert it into the heap. After each insertion, the heap still has the max-heap property, so after n Insert operations, it is a max-heap on the n elements. Then this heap construction runs in Ο(n logn) time.... .........

Suppose that instead of using Build-Heap to build a max-heap in place, the Insert operation is used n times. Starting with an empty heap, for each element, use Insert to insert it into the heap. After each insertion, the heap still has the max-heap property, so after n Insert operations, it is a max-heap on the n elements. Then this heap construction runs in Ο(n logn) time....

633 points
0
For option D) you have given the answer for number of comparisons, which i agree will be O(n log n). But after the comparison there will be swapping to place the key in the correct position, so that will take O(n^2) time. This is the sole reason why binary insertion sort requires O(n^2) time in worst case also.
0

## https://gateoverflow.in/27194/tifr2014-b-9

0
So in this case option D) will be correct or not? As it is MSQ A, B, C are already correct i know for D) i think it will be false.
0