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