# Running time complexity of Binary Search Trees and Big-Omega

I know that the main operations (Insert, Search, Delete) have a worst-case running time of $\mathcal{O} (h)$. But I wanted to dig into this deeper.

Basically I am having some difficulties understanding "Big-Omega" when it comes to the worst-case time complexity. I usually define them as follows:

Let $t(x)$ be the number of steps taken by an algorithm $\mathcal{A}$ on input $x$.

Let $T(n)$ be the worst-case running time complexity of $\mathcal{A}$.

$T(n) = max(t(x))$ where max is over all inputs x of size n.

Then $T(n) \in \mathcal{O}(g(n))$ if for every input of size $n$, $\mathcal{A}$ takes at most $c \cdot g(n)$ steps.

Moreover,

$T(n) \in \Omega(g(n))$ if for some (there exists) inputs of size $n$, $\mathcal{A}$ takes at least $c \cdot g(n)$ steps.

Returning to BSTs....

We know that for all inputs of size $n$, in the worst case, the height of the tree is $n$, which means we need to visit all $n$ nodes in the worst-case. This is the "ultimate" worst case (forgive my lack of rigour here!), meaning it cannot get any worse, and hence $\mathcal{O}(n)$ running time. But we also know that a tree may be balanced, in which case we could argue that there exists such an input (a balanced tree) such that we would take at least $\Omega(logn)$ for the running time. This is still a "worst case", but a lower bound to that worst case.

I don't feel that is quite right, nor does it make much sense. Perhaps I am just lacking an understanding of how to determine when $T(n) \in \Omega(g(n))$.

any help appreciated!

• Why do you call the balanced case as "the worst case"? Isn't it the best case for traversal? – Evil Jun 17 '17 at 1:07
• ". . . a tree may be balanced. . ." The keyword is may. A balanced binary tree is a type of binary tree; the reverse doesn't hold. Insertion's worst case runtime complexity in a binary search tree is in $O(n)$. Insertion's worst case runtime complexity in a balanced binary search tree is $O(h)$. – Christopher Bell II Jun 17 '17 at 1:13
• You need to revisit the definition of the Landau symbols. Also, our reference questions may help. – Raphael Jun 17 '17 at 8:11

Big $O$ and big $\Omega$ are not about running times, they are about the rate of growth of functions. If $f(n)$ is the worst-case running time of some operation on inputs of length $n$, then $f(n) = \Omega(g(n))$ means that there exists $C > 0$ such that for some input of length $n$, the running time is at least $Cg(n)$. The fact that we are talking about big $\Omega$ rather than big $O$ doesn't mean that we switch from worst case to best case. On the contrary, we are estimating the very same function, but from below rather than from above.
• I feel I get that. I am more trying to get an intuition, when I see an Algorithm, how can I see that the worst-case running time is bounded from below? Do I just need to show that? I guess my confusion is I feel like I'm trying $\Omega(g(n))$ as "less extreme" worst case and $O(g(n))$ as an "Extreme" worst case. If I am searching for a node in a binary tree, in the worst case it could be in the leaf nodes, which would either put the running time in either $O(n)$ or $O(logn)$, but because $logn < n$, then we can make $logn$ our lower bound? – TimelordViktorious Jun 17 '17 at 17:36
• By the way, any function which is $\Omega(n)$ is also $\Omega(\log n)$. – Yuval Filmus Jun 17 '17 at 18:05