2
$\begingroup$

If it is given that a program has a worst case running time of $O(n)$, then is it still okay to define the running time as being $O(n^2)$. By definition, this seems corrects since Big-Oh is essentially an upper bound.

But, since we already established a worst case running time, can this still be correct.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

Yes, if a program runs in time $O(n)$, then it also runs in time $O(n^2)$. However, usually we try to give the best possible bound, to prevent readers from being misled. You can signify that the bound is tight using big theta: the worst-case running time of the program is $\Theta(n)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Even though the program is defined as being the O(N) is defined as a worst case running time, then is it still possible for one to guarantee that the program also runs O(N^2) or even O(N^3). My confusion is coming from the labeling the runtime as being worse case. $\endgroup$
    – sam
    Commented Feb 19, 2015 at 14:59
  • $\begingroup$ @sam. Your confusion seems to stem from the difference between the run time of the program and the bounds on the function that expresses the run time. We agree that the run time, $T(n)$, of the program is bounded by some function, $f\in O(n)$. For example, we might have $f(n)=2n+\log n$. That function, though, is also itself in $O(n^2)$ or even $O(2^n)$. In effect, we've stepped away from the run time of the program into a context where we can also look at upper bounds on $f$, completely independent of the original program's bounds. $\endgroup$
    – Rick Decker
    Commented Feb 19, 2015 at 15:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.