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$
3
  • 2
    $\begingroup$ $T(n) \in O(n)$ does not imply $T(n) \not\in \Theta(n)$. $\endgroup$
    – Steven
    Oct 24, 2019 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, 2019 at 14:45
  • 1
    $\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, 2019 at 15:37

1 Answer 1

3
$\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$
3
  • $\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, 2019 at 14:43
  • $\begingroup$ @Gust Many people are just lazy and/or it's not worth it being precise. $\endgroup$
    – Juho
    Oct 24, 2019 at 14:57
  • $\begingroup$ I don’t think such a question has an answer, beyond people just being used to big O. $\endgroup$ Oct 24, 2019 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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