629 views
0 votes
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.

1 Answer

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

Related questions

4 votes
4 votes
1 answer
1
Shashank Chavan asked Jan 18, 2016
11,125 views
What's the difference between Binary tree height, level and depth? Sometimes it's confusing!Does there definition change according to question also, if mentioned?
2 votes
2 votes
1 answer
2
LoveCS asked Dec 5, 2017
980 views
1 votes
1 votes
0 answers
4
Rohit Gupta 8 asked Dec 25, 2017
1,109 views
If the average depth of a node in an $n$-node binary search tree is $O(\log{n})$, then the height of the tree is$O(n\log{n})$$O(n)$$O(\log{n})$$O(\sqrt(n\log{n}))$