# Use of Big-Oh in Worst case [duplicate]

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.

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)$.
• @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. Feb 19 '15 at 15:34