I have two functions $f(n) = n^{1.001}$ and $g(n) = nlog_2n$ and I want to determine if the inequality $f(n) < c*g(n)$ is true, where $f(n), g(n), c > 0$.

To do this, I am using the following property:

$f(n) < c*g(n)$ if and only if $log(f(n)) < logc + log(g(n))$


$1.001*log_2n < log_2c + log_2{(nlog_2n)}$

By setting c to 1:

$1.001*log_2n < log_2n(nlog_2n)$

I am not sure how can I solve this inequality so that I can find what the value of 'n' is.

  • $\begingroup$ It's not true (no matter the $c$), and the reason is simple. $f(n)/g(n)\to \infty$ when $n\to \infty$ $\endgroup$
    – Jakobian
    Mar 11 '19 at 22:45
  • $\begingroup$ Would it be correct to say that g(n)/f(n) → 0 when 𝑛→∞? Since f(n) grows faster than g(n)? $\endgroup$
    – ceno980
    Mar 12 '19 at 0:43

\begin{align} \lim_{n \to \infty} \frac{f(n)}{g(n)} &=\lim_{n \to \infty} \frac{n^{1.001}}{n \log_2 n} \\ &= \lim_{n \to \infty} \frac{n^{0.001}}{\log_2 n} \\ &= \ln 2 \lim_{n \to \infty} \frac{0.001 n^{-0.999}}{\frac1n} \\ &= 0.001 \ln 2 \lim_{n \to \infty } n^{0.001} \\ &= \infty \end{align}

Hence $\frac{f(n)}{g(n)}$ can't be bounded by a constant.

Also for your question in the comment, yes, $\lim_{n \to \infty}\frac{g(n)}{f(n)}=0$


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.