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.
From wikipedia, definition of big O notation:
if and only if there is a positive constant M such that for all sufficiently large values of $x$, $f(x)$ is at most M multiplied by $g(x)$ in absolute value. That is, $f(x) \in O(g(x))$ if and only if there exists a positive real number $M$ and a real number $x_0$ such that
$|f(x)|<= M |g(x)| \quad \text{for all} \; x > x_0$
What happens for functions that do not converge (to a constant nor infinity)?
Look at the functions $f(x) = |xsin(x)|$, and $g(x) = 10$
for each $x_0$, there is some $x > x0$, such that $x = k\pi$, thus $f(x) = 0$ - so for each $M$ - $Mf(x) > g(x)$ will yield false, and $g(x) \; \not\in O(f(x))$
However, it is easy to see that $|xsin(x)|$ is not bounded by any constant as well, thus for each $M$,$x_0$, there is some $x > x_0$ such that $f(x) < Mg(x)$ will also yield false, and $f(x) \not\in O(g(x))$
Note: for definition if big O that allows a maximum constant difference between $Mf(x)$ and $g(x)$, the same idea will apply with $g(x) = \log(x)$
Here's a pair monotonic functions that are not asymptotically comparable. This is relevant because most complexities arising in practice are in fact monotonic.
$$ f(x) = \Gamma( \lfloor x \rfloor + 1 ) = \lfloor x \rfloor ! $$ $$ g(x) = \Gamma( \lfloor x-1/2 \rfloor + 3/2 ) $$
Here, $ \Gamma $ is the gamma function. The second function is specially constructed to be very similar to the factorial, just "sampled" at slightly offset points in the gamma function. The functions cross each other periodically in such a way that neither is asymptotically bound by the other.
Let $\mathcal{L}$ be the class of functions obtained from the identity function and constants using the following operations: addition, subtraction, multiplication, division, logarithm and exponential. For example, $\exp(2\sqrt{\log x + \log\log x})/x^2$. Hardy proved that for every two functions $f,g \in \mathcal{L}$ which are positive and tend to infinity, one of the following is true: $f = o(g)$, $f = \omega(g)$, $f/g$ tends to a constant. See page 18 of his book "Orders of infinity".
The upshot is that any two "simple" functions occurring in the analysis of algorithm are comparable. Here "simple" means that there is no definition by cases (other than finitely many base cases), and no surprising functions appear, such as the inverse Ackermann function which sometimes figures in running times.
For completeness, here's a slightly easier version of Ambroz's answer. Not only is it strictly increasing, but smooth as well!
Intuitively, we want to construct a function that oscillates between fast-growing and slow-growing, with larger and larger swings. We'll start with $$f_0(x)=x,\quad g_0(x)=x$$
We need some oscillation, so let's tweak $f$ to be $x+\sin{x}$. That's non-decreasing, but a small tweak regains strictly increasing $$f_1(x)=2x+\sin{x},\quad g_1(x)=2x$$
We now have an additive gap. We can make that a multiplicative gap via exponentiation $$f_2(x)=2^{f_1(x)}=2^{2x+\sin{x}},\quad g_2(x)=2^{g_1(x)}=2^{2x}$$
Finally, we can replace the multiplicative gap with an "exponentiative" gap in the same way. $$f(x)=f_3(x)=2^{f_2(x)}=2^{2^{2x+\sin{x}}},\quad g(x)=g_3(x)=2^{g_2(x)}=2^{2^{2x}}$$
Whenever $\sin{x}=-1$, we get that $$f(x)=2^{2^{x-1}}=2^{0.5*2^x}=(2^{2^x})^{0.5}=g(x)^{0.5}$$
Similarly, whenever $\sin{x}=+1$, we get that $$f(x)=2^{2^{x+1}}=2^{2*2^x}=(2^{2^x})^2=g(x)^2$$
