7
$\begingroup$

One of my lectures makes the following statement:

$$( f(n)=O(n) \land f(n)\neq o(n) )\implies f(n)=\Theta(n)$$

Maybe I'm missing something in the definitions, but for example bubble sort is $O(n^2)$ and not $o(n^2)$ but it's also not $\theta(n^2)$ since it's best case run time $\Omega(n)$.

What am I missing here?

$\endgroup$
10
$\begingroup$

What you are missing is a very important point: An algorithm is never $O()$ of anything, since it is usually not a even a real-valued function.

When we say that bubble-sort is $O(n^2)$, what we mean is that in the function $f$, that represents the worst case run-time of bubble sort, is $O(n^2)$.

In this case, this function is indeed $\theta(n^2)$, since in the worst case, the run-time is bounded from below and from above by $c\cdot n^2$ for the relevant constants $c$.

To be more precise, the function that we refer to as the worst case runtime of an algorithm $A$ is defined by $$f_A(n)=\max_{x: |x|=n}\{\text{runtime of $A$ on input x}\}$$ And it is this function that we analyze for the worst case run time.

The best case run-time can be analyzed as well, of course. As you suggest, the best case run time of bubble sort is not $\theta(n^2)$, but rather $\theta(n)$.

$\endgroup$
  • $\begingroup$ So when we apply this notation, we always apply it to worst case or best case separately? Specifically, we're never talking about bounding the run time in general, but instead we're usually talking about bounding the worst case run time? $\endgroup$ – Robert S. Barnes Mar 7 '13 at 8:15
  • 4
    $\begingroup$ We apply these notation to functions. You can apply them to any function you want, including best, worst, and average running time. Many times we are interested in the best-case running time, and then we can analyze it as well. If you wish to give a bound on the running time "in general" as you phrase it, then your upper bound is the worst case running time, and the lower bound is the best case. Typically, in undergrad courses, you will be interested in the worst case run-time (sometimes the average as well). $\endgroup$ – Shaull Mar 7 '13 at 8:38
  • $\begingroup$ This answer would be good if the statement in question were true. $\endgroup$ – Raphael Mar 7 '13 at 18:04
  • 1
    $\begingroup$ Indeed. However, it is pretty clear that what confused the OP is not the fact that it's true, but rather the worst/best case running time issue. $\endgroup$ – Shaull Mar 7 '13 at 18:16
13
$\begingroup$

Tell the lecturer they're wrong. Take the function $$ f(n) = \begin{cases} n & n \text{ is even}, \\ 1 & n \text { is odd}. \end{cases} $$ This function is $O(n)$ but neither $o(n)$ nor $\Theta(n)$.

Here is a monotone example, which might be more convincing: $$ g(n) = \exp \exp \lfloor \ln \ln n \rfloor. $$

$\endgroup$
  • 1
    $\begingroup$ I have come to see this as the default pitfall in Landau-asymptotics and wish there was a nice alternative that yielded the desired relations. $\endgroup$ – Raphael Mar 7 '13 at 17:24
  • $\begingroup$ Logarithmico-exponential functions (functions constructed from $\exp$, $\log$, the field operations and constants) are linearly order with respect to the $f=o(g)$ order (see Hardy's "Orders of infinity"), so for these functions such problems cannot occur. The floor function is thus not logarithmico-exponential. $\endgroup$ – Yuval Filmus Mar 7 '13 at 17:27

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.