“It is a common misconception that Big O characterizes worst-case running time while Big Omega characterizes the best-case running time of an algorithm. There is no one-to-one relationship between any of the cases and the asymptotic notations.”
Why the upper bound does not mean worst case ?
Hi @Yuanbo
Big-O represents the upper bound of the running time of an algorithm, so it gives the worst-case complexity of an algorithm. While Big-Omega denotes the lower bound of the running time of an algorithm, it provides the best case complexity of an algorithm.
Following this statement, it is common to conclude that Big-O characterizes worst-case running time while Big Omega characterizes the best-case.
In the lesson it’s said that notations are not tied to best/worst cases, and it’s a misconception that Big O represents the worst case, I don’t quite get this if you have an example
Hi @Yuanbo,
Asymptotic notations are for functions while cases i.e best, worst and average are just type of analysis that done on algorithm. Big-Oh(asymptotic upper bound) is basically the growth rate of function while worst case is the number of operations being run during the execution of algorithm.