Ω(f(x)) and worst case analysis

Question

I'm currently reading The Algorithm Design Manual by Steven S. Skiena as my first book to algorithms.

Something in the asymptotic part is kinda of confusing to me.

Proving the Theta

The analysis above gives a quadratic-time upper bound on the running time of this simple pattern matching algorithm. To prove the theta, we must show an example where it actually does take Ω(mn) time.

Consider what happens when the text t = “aaaa . . . aaaa” is a string of n a’s, and the pattern p = “aaaa . . . aaab” is a string of m − 1 a’s followed by a b. Wherever the pattern is positioned on the text, the while loop will successfully match the first m − 1 characters before failing on the last one. There are n − m + 1 possible positions where p can sit on t without overhanging the end, so the running time is:

(n − m + 1)(m) = mn − m 2 + m = Ω(mn)

This example is clearly meant to be the worst possible running time of the algorithm, however, instead of O(mn), Ω(mn) has been used.

Isn't Ω the lower bound of the algorithm, meaning for big enough n(s) the algorithm cannot perform better than this?

If it is then why is Ω used to show the worst performance, shouldn't Big Oh be used instead?

Any help would be much appreciated.

Answer 1

I think this is a common misconception among undergraduates about $\mathcal{O}$, $\Omega$, and $\Theta$. It is not like these symbols represent worst, best, and average case running time, respectively. They are just upper and lower bounds on running times and you can have lower and upper bounds on all of those cases.

In some sense, $\Omega$ is just the pessimistic view of the worst case running time. This shows that in the worst case (e.g. the word+pattern of your problem) you cannot expect a running time that is faster than $c \cdot mn$ for some constant $c$. However, the first paragraph of Proving the Theta suggests that they also show that the algorithm is guaranteed to run in time $\mathcal{O}(mn)$, this is the optimistic view, stating that you will never find and example where the running time is worse than $c' \cdot mn$ for some constant $c'$. Both parts combined give you that the running time is in $\Theta(mn)$.

Answer 2

By showing a worst-case example, it doesn't show $O(mn)$ ... big-O is an upper bound, so when asserting a big-O runtime, it says that that algorithm takes $O(mn)$ time or better (remember that an $O(n)$ algorithm is also an $O(n^2)$ algorithm). But showing that there is an example that actually requires $kmn$ time means that the big-O runtime of $O(mn)$ cannot be any smaller function ... That is, showing an example of where an algorithm requires $kmn$ time is a way to show the algorithm cannot be any better than $kmn$, meaning it is $\Omega(km)$. And once you have both $O(mn)$ and $\Omega(km)$ then you have $\Theta(mn)$.