8
$\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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
11
$\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)$.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Mar 7, 2013 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
    Commented Mar 7, 2013 at 8:38
  • $\begingroup$ This answer would be good if the statement in question were true. $\endgroup$
    – Raphael
    Commented Mar 7, 2013 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
    Commented Mar 7, 2013 at 18:16
16
$\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. $$

Improve this answer
$\endgroup$
2
  • 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
    Commented Mar 7, 2013 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
    Commented Mar 7, 2013 at 17:27

Your Answer

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

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