When I was a computer science undergrad, this is the one video that made algorithmic complexity stick in my head, hopefully someone else finds it as useful as I did;
By default, O, omega and theta all refer to the worst case running time.
- O(n) means worst_case_run_time <= C n
- omega(n) means worst_case_run_time >= C n
- theta(n) means C1 n <= worst_case_run_time <= C2 n
(I can't remember when someone has ever looked at "best case".)
To rephrase
- "This algorithm is O(something)" means I have an upper bound on the running time on the worst inputs.
- "This algorithm is omega(something)" means I have a lower bound on the running time on the worst inputs.
- "This algorithm is theta(something)" means I have both an upper and lower bound on the running time on the worst inputs (that differ only by a constant multiple.
In particular, a lower bound does not mean "best case" (they aren't even in the same part of the sentence).
(There's also some other detail from the video like the bit representation of string length that needs a footnote but that's much less important, I think.)
It's also more nuanced than the inequality in your correction. It's a statement about limits of functions.
The implicit default of "worst-case running time" (in the context of algorithm) may actually be the source of errors like the one made in the video. For what its worth, I actually think the lim sup definition is easier because its fewer things to memorize.