Can the worst-case analysis of $f(n)$ be $\Omega(g(n))$ but not $O(g(n))$?

Question

I am struggling to wrap my head around using $\Omega$-notation to describe worst-case running time of an algorithm, or $O$-notation to describe the best-case running time. Specifically, I struggle to understand how a given function $f(n)$ can have a worst-case lower-bound of $\Omega(g(n))$ without also having $O(g(n))$ as the worst-case upper bound--that is to say, shouldn't all best-case and worst-case complexities be $\Theta(g(n))$?

The core of the issue for me is that once you are describing a case (eg worst-case), you are fixing some characteristic about the nature of the input: this is the kind of input that makes it take as long as possible. How can there be multiple analyses of this one type of input?

Answer 1

Let me split the answer to three parts, so it will hopefully clear all misundestandings you have on the concepts.

---

What are big-O and big-$\Omega$?

Big-O and big-$\Omega$ are two mqthematical properties of functions over natural numvers. Their formal definition state that:

• $f=O(g)\iff \exists c>0:\forall n: f(n)\le c\cdot g(n)$
• $f=\Omega(g) \iff \exists c>0:\forall n:f(n)\ge c\cdot g(n)$

See the difference? Big-O talks about bounding a function from above and big-$\Omega$ bounds it from below.

When we say $f=\Theta(g)$ we actually mean that $f=O(g)$ and $f=\Omega(g)$: $f$ is bounded from above it and below it, by $g$, hence it is "equivalent" to $g$.

---

Measuring running time

When we measure the running time of an algorithm, we usually mean "measure the number of steps it takes to compute the worst case scenario when the input is of size $n$". Practically, this means that we want to know what value $T(n)$ is, where $T(n)$ is define as the worst case running time.

Now you can think of $T$ as any other function. Giving a big-O bound to $T$ just means expressing an upper bound on $T(n)$ in nice terms. And giving a big-$\Omega$ bound is just nicely writing a lower bound on $T(n)$.

So essentially, if your running time is both $O(n)$ and $\Omega(n)$, then the time your algorithm takes in the worst case is "equivalent" to a linear function.

---

Intuitively, what does it say?

Im sure that a big-O bound to the running time of your algorithm is intuitive. However, what does $\Omega(n)$ represent?

Essentially what it says, is that your big-O bound is strict. It means that you have proved your analysis cannot give a better bound on the running time. This property is less useful usually, but becomes more useful the more you are unsure if the big-O bound you gave is strict enough.

For example, try to consider the running time of heapify that converts a list of numbers to a heap. Its easy to show an $O(n\log(n))$ bound, and with a little more effort you can even show an $O(n)$ bound. So how can you be sure that you cant get to, say a $O(\log(n))$ bound with even more effort? The answer is simple: we can show an $\Omega(n)$ bound on the running time of the algorithm.

Answer 2

Consider $f(n) = n^2$. Then we have $f(n) \in \Omega(n)$ but not $f(n) \in O(n)$.

However, as you stated it, it is better to give a tight bound for best and worst cases, with the $\Theta$-notation, because saying "the worst case is exactly $n^2$ operations" is a better information than "the worst case is at least $n$ operations".

Answer 3

Take a look at my other answer for a long explanation on the topic.

---

However, the short answer would be: yes, every function $f$ is $\Theta(f)$, but we want to know what that value actually is. Is that $\Theta(n)$? Or maybe its $\Theta(n^2)$? The idea is that we want some simple function that will represent the (more complex) function of the running time.