search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
0 votes
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.
in Algorithms 17 points 49 views

3 Answers

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

@Sudarshan Bandyopadh

 

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

 

https://www.youtube.com/watch?v=MhT7XmxhaCE

0 votes

@Sudarshan Bandyopadh

 

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

 

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

 

 

B) If f(n) = Ο(g(n)) and g(n) = Ο( f(n)) then f(n) = θ(g(n))

 

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

 

C) The sequence < 20, 15, 18, 7, 9, 5, 12, 3, 6, 2 > is a max-heap...

 

True ...

 

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

 

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

 

https://gateoverflow.in/1245/gate-cse-2007-question-47 

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

@Sudarshan Bandyopadh

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

 

Bubble Sort is not online (it cannot sort a stream of inputs without knowing how many items there will be) because it does not really keep track of a global maximum of the sorted elements.

When an item is inserted you will need to start the bubbling from the very beginning ...

In bubble sort in ith iteration you have n-i-1 inner iterations (n^2)/2 total, but in insertion sort you have maximum i iterations on i'th step, but i/2 on average, as you can stop inner loop earlier, after you found correct position for the current element.

So you have (sum from 0 to n) / 2 which is (n^2) / 4 total; That's why insertion sort is faster than bubble sort....

 

https://gateoverflow.in/975/gate-cse-2006-question-14-isro2011-14  

 

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

 

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

 

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

@Sudarshan Bandyopadh

 

So in this case option D) will be correct ...

0
So it means binary insertion sort takes O(n log n) in worst case?
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....
...