15
$\begingroup$

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?

$\endgroup$
21
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice! It is noteworthy, though, that periodic elements occur frequently in average case analysis (of d&c algorithm). The one I know are bound on both sides by constants, so they don't hurt asymptotic comparability. $\endgroup$ – Raphael Oct 16 '12 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy