The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
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 in DS by Active (2.3k points) | 83 views
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?
Why n/2 why not logn?
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?
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 by Active (3.3k points)

Related questions

+2 votes
1 answer
asked Dec 5, 2017 in DS by LoveCS (17 points) | 527 views
0 votes
0 answers
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
49,808 questions
54,474 answers
74,356 users