2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ What do you mean by "tight", $\Theta$ or $\sim$? $\endgroup$
    – Raphael
    Commented Mar 7, 2013 at 11:28
  • $\begingroup$ I mean $\Theta$. $\endgroup$ Commented Mar 12, 2013 at 9:07

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Commented Mar 7, 2013 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
    Commented Mar 7, 2013 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
    Commented Mar 7, 2013 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
    Commented Mar 7, 2013 at 11:39
-1
$\begingroup$

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).

$\endgroup$
1
  • 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
    Commented Mar 7, 2013 at 11:12

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.