# Why is building a heap $\mathcal O(n)$ and not $\theta(n)$?

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

• $T(n) \in O(n)$ does not imply $T(n) \not\in \Theta(n)$. – Steven Oct 24 '19 at 13:51
• 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. – Gust Oct 24 '19 at 14:45
• 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. – Steven Oct 24 '19 at 15:37

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.
• 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? – Gust Oct 24 '19 at 14:43