Q:

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

A:

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.

