n*log n and n/log n against polynomial running time

Question

I understand that $\Theta(n)$ is faster than $\Theta(n\log n)$ and slower than $\Theta(n/\log n)$. What is difficult for me to understand is how to actually compare $\Theta(n \log n)$ and $\Theta(n/\log n)$ with $\Theta(n^f)$ where $0 < f < 1$.

For example, how do we decide $\Theta(n/\log n)$ vs. $\Theta(n^{2/3})$ or $\Theta(n^{1/3})$

I would like to have some directions towards proceeding in such cases. Thank you.

Answer 1

If you just draw a couple of graphs, you'll be in good shape. Wolfram Alpha is a great resource for these kinds of investigations:

Generated by this link. Note that in the graph, log(x) is the natural logarithm, which is the reason the one graph's equation looks a little funny.

Answer 2

$\log n$ is the inverse of $2^n$. Just as $2^n$ grows faster than any polynomial $n^k$ regardless of how large a finite $k$ is, $\log n$ will grow slower than any polynomial functions $n^k$ regardless of how small a nonzero, positive $k$ is.

$n / \log n$ vs $n^k$, for $k < 1$ is identical to: $n / \log n$ vs $n / n^{1-k}$

as $n^{1-k} > \log n$ for large $n$, $n / \log n > n^k$ for $k < 1$ and large $n$.

Answer 3

For many algorithms, it sometimes happens that the constants are different, causing one or another is faster or slower for smaller data sizes, and are not as well-ordered by algorithmic complexity.

Having said that, if we only consider the super-large data sizes, ie. which one eventually wins, then O(n^f) is faster than O(n/log n) for 0 < f < 1.

A large part of algorithmic complexity is to determine which algorithm is eventually faster, thus knowing that O(n^f) is faster than O(n/log n) for 0 < f < 1, is often enough.

A general rule is that multiplying (or dividing) by log n will eventually be negligible compared to multiplying (or dividing) by n^f for any f > 0.

To show this more clearly, let us consider what happens as n increases.

   n       n / log n         n^(1/2)
   2        n/ 1              ?
   4        n/ 2             n/ 2
   8        n/ 3              ?
  16        n/ 4             n/ 4
  64        n/ 6             n/ 8
 256        n/ 8             n/16
1024        n/10             n/32

Notice which decreases more rapidly? It is the n^f column.

Even if f was closer to 1, the n^f column will just start slower, but as n doubles, the rate of change of the denominator speeds up, whereas the denominator of the n/log n column appears to change at a constant rate.

Let us plot a particular case on a graph

Source: Wolfram Alpha

I selected O(n^k) such that k is quite close to 1 (at 0.9). I also selected the constants so that initially O(n^k) is slower. However, notice that it eventually "wins" in the end, and takes less time than O(n/log n).

Answer 4

Just think of $n^f$ as $\dfrac{n}{n^{1-f}}$. So for your example, $n^{2/3}=n/n^{1/3}$. Then it is easy to compare the growth of

$$ \frac{n}{\log n} \quad \text{vs.} \quad \frac{n}{n^{1-f}}.$$

Remember that $\log n$ grows asymptotically slower than any $n^\varepsilon$, for every $\varepsilon>0$.

Answer 5

When comparing running times, it always helpful to compare them by using big values of n. For me, this helps build intuition about which function is slower

In your case think of n = 10^10 and a = .5

O(n/logn) = O(10^10/10) = O(10^9)
O(n^1/2) = O(10^10^.5) = O(10^5)

Hence, O(n^a) is faster than O(n/logn), when 0 < a < 1 I have used just one value, however, you can use multiple values to build intuition about the function

Answer 6

Let $f \prec g$ denote "f grows asymptotically slower than g", then you can use the following easy rule for polylogarithmic? functions:

$$n^{\alpha_1}(\log n)^{\alpha_2}(\log \log n)^{\alpha_3} \prec n^{\beta_1}(\log n)^{\beta_2}(\log \log n)^{\beta_3} \Longleftrightarrow (\alpha_1, \alpha_2, \alpha_3) < (\beta_1, \beta_2, \beta_3)$$

The order relation between the tuples is lexicographic. I.e. $(2, 10) < (3, 5)$ and $(2, 10) > (2, 5)$

Applied to your example:

$\mathcal{O}(n/\log n) \Rightarrow (1, -1, 0)$

$\mathcal{O}(n^{2/3}) \Rightarrow (2/3, 0, 0)$

$\mathcal{O}(n^{1/3}) \Rightarrow (1/3, 0, 0)$

$$(1/3, 0, 0) < (2/3, 0, 0) < (1, -1, 0)\\ \Rightarrow \mathcal{O}(n^{1/3}) \prec \mathcal{O}(n^{2/3}) \prec \mathcal{O}(n/\log n)$$

You could say: powers of n dominate powers of log, which dominate powers of log log.

Source: Concrete Mathematics, p. 441