1
$\begingroup$

I know that Big $O$ notation is used to describe the upper bound of running time of an algorithm, if we consider time complexity of that algorithm. However, I'm not sure why the following is not stated everytime anyone attempts to explain time complexity or Big $O$ - the fact we're looking for the least upper bound of the running time.

Correct me if I'm wrong, but $O(n!)$ is known to be the highest complexity - much worse than exponential. If I have an algorithm whose running time is $O(n)$, then it is also $O(n^2)$, $O(n^3)$, $O(2^n)$, and $O(n!)$, because they are all upper bounds of its running time (I know that, because it's $O(n)$).

So is it possible to find the least upper bound of the running time? If I read an algorithm has complexity $O(2^n)$, does it mean it has been proven this is the least upper bound? Or is it just the smallest upper bound that has been found so far?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ In your second paragraph, $O(n!)$ is by far not the highest complexity. Take, for example, the function $n!^{n!}$. For the body of your question, have you looked at $\Theta(.)$ estimates (aka, big-Theta)? They apply here. $\endgroup$
    – Rick Decker
    Dec 2, 2015 at 22:21
  • $\begingroup$ cs.stackexchange.com/q/23068/755 $\endgroup$
    – D.W. ♦
    Dec 3, 2015 at 7:07
  • $\begingroup$ @D.W. check page 23 here to see what I mean (the last sentence on that page). Running time of an algorithm can be $O(n^2)$, but how do we know if it's not $O(n)$? If somebody tells me this algorithm is $O(n^2)$, does it mean he has proven there doesn't exist a smaller upper bound, for instance $O(n)$? $\endgroup$
    – user4205580
    Dec 3, 2015 at 9:12

1 Answer 1

Reset to default
1
$\begingroup$

If you want to state that $O(f(n))$ is the best bound on the complexity that you can get, then you can use big Theta instead: $\Theta(f(n))$ stands for a function – in this case worst-case time complexity – that is asymptotically equal to $f(n)$ up to constants. That is, if the worst-case time complexity $T(n)$ satisfies $cf(n) \leq T(n) \leq Cf(n)$ for some $0<c\leq C$, then you can state that the (worst-case) time complexity of the algorithm is $\Theta(f(n))$. This implies both the upper bound $O(f(n))$ and the matching lower bound $\Omega(f(n))$, showing that the upper bound is best possible.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If bubble sort has complexity $O(n)$, does it mean it has been proven this is the least upper bound possible (meaning no smaller upper bound exists)? Or is it the least upper bound that has been found so far? $\endgroup$
    – user4205580
    Dec 3, 2015 at 19:55
  • $\begingroup$ Usually it implies that this is the least upper bound possible, though formally it's just an upper bound. $\endgroup$
    – Yuval Filmus
    Dec 4, 2015 at 3:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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