0 votes

Consider a binary tree, where left and right subtreealready heapified. But we havenot done heapificationfor root yet. Then what is time complexity to convert it in a full heap tree?

$A)O(\log n)$ or $o(n)$ $B)\Omega (\log n)$ or $\omega(n)$ $C)\Theta (\log n)$ or $\theta (n)$ $D)\text{None of these}$

$A)O(\log n)$ or $o(n)$ $B)\Omega (\log n)$ or $\omega(n)$ $C)\Theta (\log n)$ or $\theta (n)$ $D)\text{None of these}$

0

I think it should be A) because it cant take more than logn time in any case but it can be less than that, even O(1).

0

i hope, option A is more accurate... why?

we have log n levels in the heap, it is sure...

it is saying that already its left sub-tree and right sub-tree is heapified

therefore remaining is root only, on heapifying the value( initially at the root node), may go atmost the last level (log n level) ------> it is not always happens ===> Θ ( log n ) wrong

and it can not be more than log n ===> Ω( log n) cancelled, the remaining option is A

with in the A also my choice is O( log n ) due to some time it is equal to ( log n ).

we have log n levels in the heap, it is sure...

it is saying that already its left sub-tree and right sub-tree is heapified

therefore remaining is root only, on heapifying the value( initially at the root node), may go atmost the last level (log n level) ------> it is not always happens ===> Θ ( log n ) wrong

and it can not be more than log n ===> Ω( log n) cancelled, the remaining option is A

with in the A also my choice is O( log n ) due to some time it is equal to ( log n ).

0

@Shaik Masthan,

on heapifying the value( initially at the root node), may go atmost the last level (log n level) ------> it is not always happens ===> Θ ( log n ) wrong

I might be wrong, please correct me

Here, Big Oh means everything equal to or below the c.g(n) is possible but not above and even in heapify, the complexity can be below or equal to logn

Whereas, Omega means it can be logn or anything more than that.

Where did I go wrong?

0

@Vikas Verma, yes you are right... my analysis is correct but i just mis-used the terms... i will update my comment..

0

@srestha,

Yes it can't be omega logn because it would mean that the time complexity can be anywhere between logn and n^n. Whereas O logn mean it can be anywhere between O(1) and logn.

If we account for the swap time, it will be O(1) + O(logn) and still come down to O(logn)

Yes it can't be omega logn because it would mean that the time complexity can be anywhere between logn and n^n. Whereas O logn mean it can be anywhere between O(1) and logn.

If we account for the swap time, it will be O(1) + O(logn) and still come down to O(logn)

0

if you are using array for implementing heap, just replaces the values ===>O(1)

if you are using linked list for implementing heap, just update the pointers ===>O(1)

if you are using linked list for implementing heap, just update the pointers ===>O(1)

0

@Vikas @Shaik

actually in gate question only I got 2 type of answer

here it is omega(n) and in another place O(n). that is why I got confused

https://gateoverflow.in/8091/gate2015-2-17

So, according to u this question have some error?

0

As we know under any circumstances the complexity can't go above logn hence maximum TC is logn

Now coming our question, option A says either it will be equal or less OR strictly less than logn

Which sounds great because in worst case input it will be logn and for the rest of the cases it will be less than that.

Coming to the question srestha mentioned in the above comment, none other option satisfies the answer except omega log n because only that says EQUAL to or more than logn.

So in the worst case input, the best we would be able to do is logn. Anything other than that would not be the best possible solution.

Now coming our question, option A says either it will be equal or less OR strictly less than logn

Which sounds great because in worst case input it will be logn and for the rest of the cases it will be less than that.

Coming to the question srestha mentioned in the above comment, none other option satisfies the answer except omega log n because only that says EQUAL to or more than logn.

So in the worst case input, the best we would be able to do is logn. Anything other than that would not be the best possible solution.

0

@srestha,

in this question https://gateoverflow.in/8091/gate2015-2-17, they are interested in lower bound

what is lower bound for that, it is required only 1 comparission operation, i mean root is already satisfied

therefore your complexity = constant

T(n) = Ώ( log n)

But in your question, generally we do for upper bound = log n in our case,

T(n) = O ( log n)

0

I think that the answer should be A, as per the question both the left sub tree and the right sub tree are already heapified. Which means that the root node is the only one on which we have to perform the heapify operation.

1) The **worst case** will be when it can traverse upto the leaf node, i.e in worst case it will take O(logn).

2) The **best case** will be when the root is already at the best place that means its position is not going to change i.e will take O(1).

So, finally the time taken would be between O(logn) to O(1).

**Please correct me if i am wrong.**

0

what is lower bound for that, it is required only 1 comparission operation, i mean root is already satisfied

then theta should be better

and lower bound and upper bound, does it really do any change in complexity

I think it will be better for theta i.e. avg case algo

and lower bound and upper bound almost it matter nothing to find TC

0

Yes I also think option a would be correct one time complexity will be less than logn or equal to logn here