The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
33 views
For a heap containing n elements,smallest element can be found in n/2 operations.I always get confused and think as logn operations.Please help me differentiating between these two times.
asked ago in DS by Junior (509 points) | 33 views
0
For a minheap, it can be found in O(1) but in case of maxheap, we just need to search the last n/2 elements and find it. What's confusing here?
0
Why n/2 why not logn?
0
Time taken to find the smallest element in an array having n elements is O(n).
So to find the smallest element in the array of size ${n}/_{2}$ will be O(n/2) isn't it?
0
In max heap, a small element may be present on either left or right we don't know hence we need to check left children as well as right children, in height of 2 max heap there can be max 4 leaf nodes and hence we need to check all of them. so height of 2 can contain 7 nodes out of which we need to check 4 leaf nodes to find smallest which is approximately equal to n/2..

If you notice the arrangement of array elements you fill find all leaf nodes are present in next half of the array. Hence you need scan n/2 elements to find smallest. actually it is floor(n/2)+1 where you can get position of the first leaf node.

In balanced binary search tree you can find minimum in logn time as we know for sure smallest will always be present on the left side. Hence time require to search element.

Where as in binary search tree it might take n comparisons to check for smallest element if its a skew tree.

1 Answer

0 votes
Just remember one simple funda.

Whenever we are dividing "n" or any given variable by 2 till it reaches to the certain value or mostly 0. Then the complexity is logn.

But in the above case, you are just finding the smallest element in the array of size n/2 and not dividing changing n again and again.

So complexity will be equal to O(n/2) = O(n).
answered ago by Junior (909 points)

Related questions

+1 vote
1 answer
1
+2 votes
1 answer
2
asked Dec 5, 2017 in DS by LoveCS (31 points) | 356 views
0 votes
0 answers
3


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

42,294 questions
48,415 answers
153,516 comments
62,660 users