1
$\begingroup$

From what I see online, all seem to suggest that heapifying takes $\mathcal O (n)$ time, but it seems like it should always takes $\theta(n)$ time, even in the best case. Is something wrong with my pseudocode? Is there a more optimized way to do heapification?

Heapification(H[1...n])
for i <- floor(n/2) downto 1 do
  k <-i; v <- H[k]
  heap <- False 
  while !heap && 2k <= n do
    j <- 2k
    if j <= n
      if H[j] < H[j+1] 
        j <- j+1
      if H[j] > v 
        H[k] <- H[j]
        k <- j
      else heap <- true
  H[k] <- v
$\endgroup$
  • 1
    $\begingroup$ $T(n) \in O(n)$ does not imply $T(n) \not\in \Theta(n)$. $\endgroup$ – Steven Oct 24 '19 at 13:51
  • $\begingroup$ But in this case it would provide more information to say $\Theta(n)$ than $O(n)$, no? It seems like it should be put in $\Theta(n)$ if it can be. $\endgroup$ – Gust Oct 24 '19 at 14:45
  • $\begingroup$ Yeah, $\Theta(n)$ would be "more precise" (in the sense that $\Theta(n) \subset O(n)$). But the focus is usually on the worst-case complexity of algorithms. Also $\Omega(n)$ is a trivial lower bound since each node of the heap must be examined at least once. $\endgroup$ – Steven Oct 24 '19 at 15:37
2
$\begingroup$

Time complexity of algorithms is usually given as big O. There are many reasons for this, including tradition, but when pertinent reason is that in some cases the time complexity depends on the input. For example, a sorting algorithm might run in $O(n\log n)$ in the worst case, but in $O(n)$ in the best case, and so it is not correct to say that it runs in $\Theta(n\log n)$.

In your particular case, your algorithm runs not only in $O(n)$ but also in $\Theta(n)$. Stating that it runs in $O(n)$ doesn't rule out a matching lower bound — it just doesn't tell the complete story.

$\endgroup$
  • $\begingroup$ Here's my question then -- then why not state $\Theta(n)$, if that is more "precise" and can conveniently provide both an upper and lower bound? $\endgroup$ – Gust Oct 24 '19 at 14:43
  • $\begingroup$ @Gust Many people are just lazy and/or it's not worth it being precise. $\endgroup$ – Juho Oct 24 '19 at 14:57
  • $\begingroup$ I don’t think such a question has an answer, beyond people just being used to big O. $\endgroup$ – Yuval Filmus Oct 24 '19 at 15:04

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.