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$
2
  • $\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$ Commented Feb 10, 2016 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$ Commented Feb 10, 2016 at 6:40

2 Answers 2

Reset to default
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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.