How to understand difference between n/2 and log(n) when comes to operations on a binary tree

Question

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.

Comments

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.

Answer 1

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