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

2 Answers

Best answer
2 votes
2 votes
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.
selected by
0 votes
0 votes

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.

Related questions

0 votes
0 votes
1 answer
2
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Apr 4, 2019
255 views
Prove that the running time of an algorithm is $\Theta (g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n))$.
0 votes
0 votes
1 answer
4