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!
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 &gt; 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.