1
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.