Are the functions always asymptotically comparable?

When we compare the complexity of two algorithms, it is usually the case that either $f(n) = O(g(n))$ or $g(n) = O(f(n))$ (possibly both), where $f$ and $g$ are the running times (for example) of the two algorithms.

Is this always the case? That is, does at least one of the relationships $f(n) = O(g(n))$ and $g(n) = O(f(n))$ always hold, that is for general functions $f$,$g$? If not, which assumptions do we have to make, and (why) is it ok when we talk about algorithm running times?

Not every pair of functions is comparable with $O(\cdot)$ notation; consider the functions $f(n) = n$ and
$$
g(n) = \begin{cases}
1 & \text{if $n$ is odd},
\\\
n^2 & \text{if $n$ is even}.
\end{cases}
$$
Moreover, functions like $g(n)$ do actually arise as running times of algorithms. Consider the obvious brute-force algorithm to determine whether a given integer $n$ is prime:

IsPrime(n):
  for i ← 2 to (n-1)
     if i·⌊n/i⌋ = n
        return False
  return True

This algorithm requires $\Theta(1)$ arithmetic operations when $n$ is even, $O(\sqrt{n})$ operations when $n$ is composite, but $\Theta(n)$ operations when $n$ is prime. Thus, formally, this algorithm is incomparable with an algorithm that uses $\sqrt{n}$ arithmetic operations for every $n$.

Most of the time when we analyze algorithms, we only want an asymptotic upper bound of the form $O(f(n))$ for some relatively simple function $f$. For example, most textbooks would simply (and correctly) report that IsPrime(n) runs in $O(n)$ arithmetic operations. Typical upper bound functions are products of exponentials, polynomials, and logarithms (although more exotic beasts like factorials and iterated logarithms also show up occasionally). It is not hard to prove that any two such functions are comparable.

See also this MathOverflow question.

StackExchange Computer Science Q#1780, answer score: 23