@Sudarshan Bandyopadh

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

0 votes

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

- If
*f*(*n*) = Ο(*g*(*n*)) and*g*(*n*) = Ο(*h*(*n*)), then*h*(*n*) = Ω(*f*(*n*))

- If
*f*(*n*) = Ο(*g*(*n*)) and*g*(*n*) = Ο(*f*(*n*)) then*f*(*n*) = θ(*g*(*n*)) - The sequence < 20, 15, 18, 7, 9, 5, 12, 3, 6, 2 > is a max-heap.
- 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.

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.

0

@Sudarshan Bandyopadh

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).

0 votes

@Sudarshan Bandyopadh

http://www.columbia.edu/~cs2035/courses/csor4231.F11/mathbasics.pdf

0 votes

@Sudarshan Bandyopadh

https://gateoverflow.in/11232/let-f-n-%CF%89-n-g-n-o-n-and-h-n-%D1%B3-n

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

https://gateoverflow.in/39004/madeeasy-test-series-algorithms-asymptotic-notations

https://gateoverflow.in/3587/gate-it-2006-question-44

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....

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

@Sudarshan Bandyopadh

https://gateoverflow.in/16831/average-number-comparisons-binary-search-consecutive-starting

https://stackoverflow.com/questions/17270628/insertion-sort-vs-bubble-sort-algorithms

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

Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2(n)⌉ comparisons in the worst case, which is O(n log n). The algorithm as a whole still has a running time of O(n2) on average because of the series of swaps required for each insertion....