1
$\begingroup$

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!

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Why do you call the balanced case as "the worst case"? Isn't it the best case for traversal? $\endgroup$ – Evil Jun 17 '17 at 1:07
  • $\begingroup$ ". . . 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)$. $\endgroup$ – Christopher Bell II Jun 17 '17 at 1:13
  • 1
    $\begingroup$ You need to revisit the definition of the Landau symbols. Also, our reference questions may help. $\endgroup$ – Raphael♦ Jun 17 '17 at 8:11
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – TimelordViktorious Jun 17 '17 at 17:36
  • $\begingroup$ Actually your statement was right, and mine wrong... corrected now. $\endgroup$ – Yuval Filmus Jun 17 '17 at 18:04
  • $\begingroup$ By the way, any function which is $\Omega(n)$ is also $\Omega(\log n)$. $\endgroup$ – Yuval Filmus Jun 17 '17 at 18:05
  • $\begingroup$ I'm not sure that's true... Ω is a tight lower bound. It's true that O(n) function are O(logn), but not with Ω $\endgroup$ – user2593758 Feb 3 '19 at 19:46
  • $\begingroup$ I’m afraid it’s not a tight lower bound. Just a lower bound. $\endgroup$ – Yuval Filmus Feb 4 '19 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.