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.