4
$\begingroup$

When discussing the worst case runtime $T(n)$ of an algorithm, we attempt to bound $T(n)$ above by some simple function $g(n)$, so that $T(n) = O(g(n))$. When discussing the best case runtime $T(n)$ of an algorithm, we also attempt to bound $T(n)$ above and use $O$ notation.

Why don't we instead attempt to bound the best case runtime from below? Wouldn't it make more sense to put an upper bound on the worst case runtime and a lower bound on the best case runtime, as this will then give us upper and lower bounds on all cases?

I understand that both $O$ and $\Omega$ notations can be useful for discussing best/worst/average case runtime., and that we can put upper and lower bounds on the worst or best case runtimes, respectively. My question is about the convention in the field to list an upper bound rather than a lower bound for the best case runtime (for example, see here and here).

$\endgroup$
  • 4
    $\begingroup$ Possible duplicate of How does one know which notation of time complexity analysis to use? $\endgroup$ – David Richerby May 8 '16 at 5:19
  • 1
    $\begingroup$ Actually, it would be really great if we could find a simple function $g$ such that $T(n) = \Theta(g(n))$. Only an upper bound or only a lower bound are strictly worse than an asymptotically tight bound. $\endgroup$ – Yuval Filmus May 8 '16 at 9:06
  • $\begingroup$ We usually don't even care about best cases of algorithms, let alone their lower bounds... $\endgroup$ – effeffe May 8 '16 at 10:23
3
$\begingroup$

$O$ upper bounds how quickly a function grows, while $\Omega$ lower bounds how quickly a function grows. This a completely separate issue from whether one's considering worst/average/best case runtime analysis, although this distinction causes confusion. Usually we care most about upper bounding the runtime of an algorithm, which is why you'll likely see $O$ bounds most often regardless of which notion of runtime is being considered.

$\endgroup$
  • $\begingroup$ I understand the two notions are distinct, but I don't see why they are completely separate. If $W$ and $B$ are respectively the worst and best case runtimes of an algorithm, do we not have $B = O(W)$ and $W = \Omega(B)$? And since $O$ and $\Omega$ are transitive, knowing $O(W)$ gives us a (possibly loose) definition of $O(B)$, and similarly $\Omega(B)$ gives us a (possibly loose) definition of $\Omega(W)$. $\endgroup$ – agcha May 8 '16 at 1:40
  • $\begingroup$ "Usually we care most about upper bounding the runtime of an algorithm." Why do we care about putting an upper bound on the best case more than putting a lower bound on the best case? $\endgroup$ – agcha May 8 '16 at 1:48
  • $\begingroup$ "Care more" is subjective. Both lower and upper bounds can be interesting. FWIW, best-case analysis is not studied very often to begin with; I expect that you were looking at a table of sorting algorithms or something. $\endgroup$ – Huck Bennett May 8 '16 at 2:10
  • $\begingroup$ We care about both - how good the given algorithm for the given problem in worst and average cases (using $O$), and how difficult the given problem is for any algorithm (here $\Omega$ goes). An instance of a problem, which can be a best case for the given algorithm, isn't very interesting - this and this is a best case, now what? $\endgroup$ – HEKTO May 8 '16 at 2:10
3
$\begingroup$

The symbols $O$, $\Omega$ and $\Theta$ mean at most, at least and exactly, respectively. What these bounds are about, is an entirely separate issue. They can be about best-case or worst-case performance, but you can use these symbols throughout mathematics. To describe a function, one of the things you can do is to give $O$ and $\Omega$ upper and lower bounds, independent of whether your function is related to computer science.

For example, to describe an complicated algorithm (or language) for which you don't have precise bounds yet, but for which you do have rough preliminary bounds, you can say: the best-case of this algorithm runs in $\Omega(n^2)$ and $O(n^3)$ (meaning no better than $n^2$ but no worse than $n^3$) and the worst-case runs in $\Omega(2^{\sqrt{n}})$ and $O(2^{n^{2}})$. This means: I don't know what the worst-case running time is exactly, but my analysis thus far puts it between $2^{\sqrt{n}}$ and $2^{n^{2}}$. Later, it may turn out that the worst-case running time was in fact $\Theta(2^{n})$, and then your $O(2^{n^{2}})$ upper bound, while correct, was not strict.

$\endgroup$
-1
$\begingroup$

Big O is used mostly because we want to make sure that the best case time complexity $T(n)$ will never exceed the upper bound time complexity $Cg(n)$. It would be meaningless to talk about big $\Omega$ notation because what we want is a upper bound on $T(n)$.

$\endgroup$
  • 1
    $\begingroup$ On the contrary, it does make sense to use $\Omega$ for the best-case time-complexity sometimes because we may also want a boundary that will restrict the bast-cases to go under it. For example, following @Lieuwe, I could have preliminary bounds of a complicate algorithm, such as the best-cases runs in $\Omega(n)$ and $O(n^4)$. Later on, I could improve them to $\Omega(n^2)$ and $O(n^3)$. In this way, I am able to show our understanding about the best-cases as well as our progress in our understanding. (Symmetrically, it also make sense to use $O$ in the worst-cases.) $\endgroup$ – Apass.Jack Sep 6 '18 at 23:46
  • $\begingroup$ @Apass.jack ,which notation to be used depends on the person who wants to analyse a particular algorithm.I answered the question in a broad way that is we mostly care about upper bound time complexity. i am completely agree with your comment but it is specific to a particular person, in general we mostly look for worst time complexities in best cases. $\endgroup$ – user10086840 Sep 7 '18 at 4:37
  • $\begingroup$ "in general we mostly look for worst time complexities in best cases". Well, that is your point in general. I would not mind if you say, "I am in general looking for worst time complexities in best cases". However, for me, practicing programming for tens of years, I am often looking for the (tight) best time complexities in best cases for various reasons. So, I for one, cannot agree to anyone saying the other way in general unless they can show a poll result (Please do tell me you do have a poll result). $\endgroup$ – Apass.Jack Sep 7 '18 at 4:57
  • $\begingroup$ In fact, think about what do we mean by best-cases. We are trying to find the best time complexities possible, although as tight as possible as well. So it is natural, at least for me, to try to find the best time complexities in the best-cases. Note that symmetrically, we often looks for the worst time complexity in worst-cases. $\endgroup$ – Apass.Jack Sep 7 '18 at 4:59
  • $\begingroup$ @Apass.Jack I said that, by not considering a poll result instead the question itself says that generally we use 'big O' over 'big omega'. Since it is upvoted 4 times , i assumes that mostly we use 'big O' and the natural answer to it would be what i have written in the answer. Again i would say that you uses 'big omega' for your own particular purpose, may be outer world do not uses 'big omega'..who knows?...it is specific $\endgroup$ – user10086840 Sep 7 '18 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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