# Asymptotic bound of a heap's height

Today I was taught that since the height of a heap cannot exceed $$\log n$$, it is $$O(\log n)$$; height in my class was defined as the maximum number of steps in a simple path from a leaf to the root. That is fine, but I think we should further specify it as $$\Theta(\log n)$$ since it, at that same time, must be greater than $$\log n - 1$$, and hence also fits $$\Omega(\log n)$$. I suggested this after class, but I was repeatedly told that $$O(\log n)$$ was correct, and the correctness of $$\Theta(\log n)$$ was not explicitly confirmed.

Is $$\Theta(\log n)$$ correct? If so is there a common reason / justification to just use $$O$$ instead, and possibly even to avoid using $$\Theta$$?

Clarification: it's a binary heap.

• Is it a binary heap? – Navjot Waraich Sep 25 '18 at 11:56
• @JotWaraich yep it is – busukxuan Sep 25 '18 at 11:58

Yes $$\Theta(logn)$$ is correct. By the definition of $$\Theta$$ notation we can say that some function $$g(n)$$ is at least $$k_1⋅f(n)$$ and also it is at most $$k_2⋅f(n)$$ for considerably large $$n$$ and $$k_1 > 0$$ and $$k_2 > 0$$. If you apply this definition to the heap's height, you will find that the heap's height satisfies this. So, $$\Theta(logn)$$ is totally correct.