2
$\begingroup$

I was trying to understand how to compare the big-O growth of two functions by taking the logarithm (or some increasing function like $\sqrt{f(n)}$. For example, take $2^{({log_2n})^2}$ vs $ n^{log_2n} $. Just seeing the functions as they stand, its not obvious which one grows faster than the other. However, if we take the logs:

$$ log( f_1(n) ) = log(2^{({log_2n})^2}) = ({log_2n})^2log(2) = O(({log_2n})^2)$$

and

$$ log( f_2(n) ) = log( n^{log_2n} ) = log_2(n)log(n) = O( ({log_2n})^2 )$$

which shows that the two functions grow at the same speed. So the trick of taking logs can sometimes be useful.

However, notice how it can fail, for example:

$$ g_1(n) = n^2$$

vs

$$ g_2(n) = n^3$$

if we take logs we get:

$$ log( g_1(n) ) = log( n^2 ) = 2log(n)$$

and

$$ log( g_2(n) ) = log ( n^3 ) = 3log(n)$$

using the above reasoning, it would be obvious that something is wrong since before taking the logs, the two functions were clearly growing at different rates but then taking the logs made things confusing and now it looks they are within a constant factor of each other.

My question, when is it correct to take logs to make asymptotic comparisons and why?

I was told that:

functions are asymptotically the same only if they are within a constant additive factor of each other.

But I am not sure what that statement means rigorously so I don't know what it really means. Maybe an explanation and an example would be helpful.

(for context I saw this in a CS class teaching big O notations etc).

$\endgroup$
  • $\begingroup$ In your first example the two functions are equal because $2^{(\log_2 n)^2}=(2^{\log_2n})^{\log_2n}=n^{\log_2n}$ because $2^{\log_2n}=n.$ $\endgroup$ – DanielWainfleet Feb 10 '16 at 6:16
  • $\begingroup$ The usual notation is that $f(x)\sim g(x)\iff \lim_{x\to \infty}f(x)/g(x)=1$, most commonly seen when $g(x)\to \infty$ as $x\to \infty$. And "$f(x)=O(g(x))$ as $x\to \infty $" means that $\exists K>0 \;\exists r\; (x>r\implies |f(x)|\leq K|g(x)|).$ $\endgroup$ – DanielWainfleet Feb 10 '16 at 6:40
1
$\begingroup$

If in the long run $\log_2 f(n)\lt \log_2g(n)+c$ for some constant $c$, then in the long run we have $$2^{\log_2 f(n)}\lt 2^{\log g(n)+c},$$ or equivalently $f(n)\lt 2^c g(n)$, that is, $f(n)=O(g(n))$.

$\endgroup$
0
$\begingroup$

Taking logs may disguise higher growth, as $\log f(x)=O(\log g(x))$ does not imply $f(x)=O(g(x)).$

We have $k\log y=\log y^k.$ If $k>1$ and $\log f(x)\geq k\log g(x)$ for all sufficiently large $x$ then $f(x)\geq g(x)^k$ for all large $x,$ so if $g(x)$ tends to $\infty$ then $f(x)/g(x)$ goes to $\infty$ also.

But we may also have $k^*\log g(x)>\log f(x)$ for all $x$, for some $k^*>k$, so $\log f(x)=O(\log g(x)).$

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