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!