extract and delete in heap with $O(\log n)$

Question

I had a test in Algorithms and I had this simple statement which I need to prove/disprove:

"delete and extract in minimum heap operate in $O(n)$"

I wrote that this is not true and it is $O(\log n)$. But I think thay tried to misleading me because they wrote $O(n)$ and not $θ(n)$.

The definition of $O(g(n))$ is: all the functions $f(n)$ which there are $c,n_0>0$ that $0\leq f(n)\le c*g(n)$ for every $n>n_0$. So extract from a heap is $O(n)$.

What do you think?

Answer 1

That's a tough one, because many computer scientists are sloppy, and informally use $O(n)$ to mean $\Theta(n)$, or to mean "I think it's $\Theta(n)$, but can't really prove it easily, and if it's less than $O(n)$, you're gonna need a better algorithm to demonstrate it."

For a test question, however, I'd say that your second thoughts --- that they're trying to fool you --- are correct. Certainly every function in $O(n \mapsto \log n)$ is also in $O(n \mapsto n)$, so saying that the runtime of delete and extract are in $O(n \mapsto n)$ is correct.

Answer 2

A complexity in $O(\log n)$ is also in $O(n)$, so that the statement is true. One could add "but this is not tight".