Chapter 3 Exercise 3.1-3, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

3.1-3 Explain why the statement, “The running time of algorithm A is at $$O(n^2)$$  ,” is meaningless.

Solution: Let us assume the running time of the algorithm is T(n). Now, by definition, O-notation gives an upper bound for growth of functions but it doesn’t specifies the order of growth. Therefore, saying $$T(n) \ge O(n^2)$$ means growth of T(n) is greater than some upper bound which is meaningless as we do not have any idea about what we are comparing it with.

For example, $$f(n) = 0$$ is $$O(n^2)$$ for all n. So, $$T(n) \ge f(n)$$   doesn’t tell us anything new as all running times are non-negative.