patternModerate
The running time of algorithm is at most $O(n^2)$
Viewed 0 times
thetimealgorithmrunningmost
Problem
The problem is that if an algorithm is $O(n^2)$ then it is also $O(n^3)$ and $O(n^4), O(n^n), \ldots$ and the phrase 'at most' does not make sense in this situation.
For this reason, I am not sure whether this statement is correct or not.
For this reason, I am not sure whether this statement is correct or not.
Solution
The two phrases
The running time is $O(n^2)$
and
The running time is at most $O(n^2)$
mean the same thing.
This is similar to the following two equivalent claims:
Why would we ever use "at most $O(n^2)$", then? Sometimes we want to stress that the bound $O(n^2)$ is loose, and then it makes sense to use "at most $O(n^2)$". For example, suppose that we have a multi-part algorithm, which we want to show runs in time $O(n^2)$. Suppose that we can bound the running time of the first step by $O(n)$. We could say "the first part runs in $O(n)$, which is at most $O(n^2)$".
The running time is $O(n^2)$
and
The running time is at most $O(n^2)$
mean the same thing.
This is similar to the following two equivalent claims:
- $x = y$ for some $y \leq z$.
- $x \leq y$ for some $y \leq z$.
Why would we ever use "at most $O(n^2)$", then? Sometimes we want to stress that the bound $O(n^2)$ is loose, and then it makes sense to use "at most $O(n^2)$". For example, suppose that we have a multi-part algorithm, which we want to show runs in time $O(n^2)$. Suppose that we can bound the running time of the first step by $O(n)$. We could say "the first part runs in $O(n)$, which is at most $O(n^2)$".
Context
StackExchange Computer Science Q#131789, answer score: 12
Revisions (0)
No revisions yet.