Big O vs. Big Theta for AVL tree operations

Question

On the Wikipedia page for AVL trees, the time/space complexity for common operations is stated both for average case (in Big Theta) and worst case (in Big O) scenarios. I understand both Big O and Big Theta in general but am having trouble understanding why they are used in such a way here. A source is linked but it does not seem to make any reference to Big Theta, only Big O.

For example, why is the space complexity for the tree $\Theta(n)$ in the average case but $\mathrm{O}(n)$ in the worst case? My thought process is that since you always have to store all $n$ nodes in the tree, the space complexity is both $\Omega(n)$ and $\mathrm{O}(n)$, hence it should be $\Theta(n)$ in all cases. I don't see how there can be a "worst case" in terms of space when you're always storing the same amount of data.

Similarly, for searching, why is the time complexity $\Theta(\log n)$ for the average case but $\mathrm{O}(\log n)$ in the worst case? To me this seems to imply you need to check at least some multiple of $\log n$ nodes in the average case, but not in the worst case? If the worst case is not bounded below by some multiple of $\log n$ (so could be lower in some cases), is this not a better scenario than what is given for the average case? Should it not be the other way round? It's a similar situation for insertion.

I'm not sure what I'm misunderstanding about the operation of AVL trees, average vs. worst cases, or perhaps asymptotic notation in general, that's causing this misunderstanding. Is it just always convention to state worst case in terms of Big O?

Answer 1

This is a pedantic point which I suggest ignoring.

The intended interpretation of the "worst case" column seems not to be the worst-case complexity, but rather bounds on the complexity which are true always. For example, Search always takes time $O(\log n)$; it doesn't always take time $\Theta(\log n)$.

It's true that the worst-case complexity is $\Theta(\log n)$, but usually we think of it a bit differently: $O(\log n)$ is a tight upper bound on the running time of Search. This means that $O(\log n)$ is a valid bound on the running time of Search, and that we can't improve it to $O(f(n))$ for any $f(n) = o(\log n)$.