I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds, but are there actually common algorithms in computer science that don't have asymptotically tight bounds on their worst case running times?

  • $\begingroup$ What do you mean by "tight", $\Theta$ or $\sim$? $\endgroup$ – Raphael Mar 7 '13 at 11:28
  • $\begingroup$ I mean $\Theta$. $\endgroup$ – Robert S. Barnes Mar 12 '13 at 9:07

This is somewhat of an anomaly, but yes - technically you could say that there are such algorithms. For example, consider an algorithm that checks whether a number in unary encoding is a prime - the first thing the algorithm can check is whether the number is even, this takes $O(n)$ time.

If it is, the algorithm rejects, otherwise it applies some primality test that takes $\omega(n)$ (at the very least by first converting it to binary, which takes $\theta(n\log n)$).

The point is that on every input of even length, the algorithm stops "quickly", so there is no asymptotically tight bound.

But this is clearly a stupid example. One way to avoid this problem is to define the running time of an algorithm on inputs of length $n$ to be the worst case running time on inputs of length at most $n$. This way you can get a tight bound.

  • $\begingroup$ Ok, so from a practical point of view, as an undergrad student studying from Kormen's book and using his definitions, then the worst case running time of anything I run into will pretty much always be theta of something? $\endgroup$ – Robert S. Barnes Mar 7 '13 at 9:07
  • $\begingroup$ I think that in the vast majority - yes. This is partially because for most of the algorithms, large inputs "contain" smaller inputs. For example - the set of graphs with $n$ vertices contains, in a way, the set of graphs with $n-1$ vertices, so most algorithms will perform worse on the former. But keep it in mind that you may encounter these situation at some point, although unlikely. $\endgroup$ – Shaull Mar 7 '13 at 9:11
  • $\begingroup$ "But this is clearly a stupid example." -- I think systematically overestimating runtimes and then claiming to have a tight bound is more stupid. $\endgroup$ – Raphael Mar 7 '13 at 11:28
  • 1
    $\begingroup$ Well, this "more stupid" way is usually unnecessary, since indeed large inputs contain smaller ones. And if you don't have an asymptotic tight bound and you want to force one, you'll have to do something forced. As Tom Lehrer said: "you ask a silly question, you get a silly answer". $\endgroup$ – Shaull Mar 7 '13 at 11:39

A real-life example is any of the simple sorting algorithms. E.g. insertion sort takes $\Omega(n)$ and $O(n^2)$, and those bounds can't be improved (best case is already ordered, in which case it just checks it is ordered in linear time; worst case is reverse order, and the time is quadratic).

  • 1
    $\begingroup$ In the worst case, insertion sort is $\theta(n^2)$. The question is whether there are algorithms where even in the worst case you don't have a tight bound. $\endgroup$ – Shaull Mar 7 '13 at 11:12

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.