[Solved]: Common Algorithms without Asymptotically Tight Bounds

Problem Detail: 

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?

Asked By : Robert S. Barnes

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10354