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

2 Comments

edited by
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.
0
0
How’s bigO meaning worst case? Do you have any “standard” reference for it?
0
0

2 Answers

2 votes
2 votes
Best answer
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

1 comment

How can the given statement be made meaningful?
0
0
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