175 views
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}$
in DS | 175 views
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 ).
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
@Vikas

do u mean Omega n wrong?

because it cannot go more than log n? Plz explain more
0
yes Omega(n) is wrong...
0

@Shaik

where is switching time of last element to root?

is it O(1)?because

Deleting in a heap, why does this implementation switch the values of the last element, not just replace it?

0
mam, i didn't get what do you mean exactly?

did you mean time for SWAPS?
0
yes ,swaps last predecessor to the deleted place
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)
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)
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.
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

https://gateoverflow.in/1026/gate2004-29?show=173010

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

how here  f1(n) slower than f2(n)?

plz chk

https://gateoverflow.in/177712/running-time

0
0
srestha is it A na ? what is conclusion

+1 vote