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

edited
Big-O is used to analyze  the worst case of a particular algorithm. There is no point in finding the lower bound of the worst case.
How’s bigO meaning worst case? Do you have any “standard” reference for it?

Let T(n) be the running time for algorithm A and let a function $f(n) = O(n^{2})$. The statement says that T(n) is at least $O(n^{2})$. That is, T(n) is an upper bound of f(n). Since f(n) could be any function “smaller” (as per definition of bigO) than $n^{2}$ (including constant function), we can rephrase the statement as “The running time of algorithm A is at least constant.” This is meaningless because the running time for every algorithm is at least constant.

### 1 comment

How can the given statement be made meaningful?

The short intuitive answer is that the big-O notation is used to express upper bounds on (e.g) runtime. Saying that the runtime is 'at least (some upper bound)' is peculiar and confusing - it means we are saying an upper bound is a lower bound.