# Ω(f(x)) and worst case analysis

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

Something in the asymptotic part is kind 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 \ldots aaaa”$$ is a string of $$n$$ $$a$$’s, and the pattern $$p = “aaaa \ldots 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.

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)$$.

• Thanks, got my answer. :-) Commented Jan 19, 2021 at 10:51

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)$$.

• Thank you :-) . Commented Jan 19, 2021 at 10:52

One thing I would like to add is that $$O$$, $$\Omega$$, $$o$$, $$\omega$$, and $$\Theta$$ are all about relating functions to one another. In particular for functions $$f$$ and $$g$$, $$f(x)\in O(g(x))$$ says that (in some sense) $$g(x)$$ is an upper bound for the function $$f(x)$$, and $$f(x) \in\Omega(g(x))$$ says that (in some sense) $$g(x)$$ is a lower bound for $$f(x)$$.

In the context of computer science and runtime analysis, the function $$f$$ that we care about is (usually) the function that takes in a natural number $$n$$ and returns the maximum running time of an algorithm on any instance of size $$n$$. When we say that an algorithms running time is $$O(g(n))$$ or $$\Omega(g(n))$$ what we actually mean is that this "worst-case running time" function is $$O(g(n))$$ or $$\Omega(g(n))$$. So, for an algorithm to be $$\Omega(g(n))$$, we don't need to show that the running time is lower bounded by $$g(n)$$ for every instance of size $$n$$, just for at least one instance.