13
$\begingroup$

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.

$\endgroup$

migrated from stackoverflow.com Sep 15 '12 at 15:05

This question came from our site for professional and enthusiast programmers.

3
$\begingroup$

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:

equations

Graph

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.

$\endgroup$
10
$\begingroup$

$\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$.

$\endgroup$
3
$\begingroup$

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

enter image description here enter image description here

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

$\endgroup$
  • $\begingroup$ what about n/log n $\endgroup$ – mihsathe Sep 8 '12 at 3:42
  • $\begingroup$ That was a bit of a typo, that's what I meant in the beginning. Anyways, I added a more appropriate graph that shows n^k eventually being faster, even if constants are selected such that it is initially slower. $\endgroup$ – ronalchn Sep 8 '12 at 4:06
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Don't write O(10^9), but the main point about trying some numbers to build intuition is right. $\endgroup$ – Steve Jessop Sep 8 '12 at 4:19
  • $\begingroup$ Fail. This is not correct. You substituted a single n constant, which may be biased. If I chose different constants, I could make any algorithm look better. Big O notation is used to establish trends in what will be faster in the long term. To do this, you have to be able to show that it is faster for large n, even if it is slower when n is smaller. $\endgroup$ – ronalchn Sep 8 '12 at 4:20
  • $\begingroup$ Thanks. Added multiple values part and to consider bigger numbers $\endgroup$ – Himanshu Jindal Sep 8 '12 at 4:25
  • $\begingroup$ It should be noted that just because f(a) > g(a) for some constant a, does not necessarily imply that O(f(x)) > O(g(x)). This is useful to build intuition, but is insufficient to compose a rigorous proof. In order to show that this relationship holds, you must show this to be true for ALL large n, not just one large n. Likewise, you must show it to be true for all polynomials of positive degree < 1. $\endgroup$ – user1512185 Sep 8 '12 at 4:26
1
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.