time complexity

Question

$f(n)=2n^2+ n log n$

$g(n)= \dfrac{n}{logn} + log^2n$ then 

$f(n)\times g(n)$ is:

• A. $n^2logn$
• B. $\dfrac{n^3}{logn}$
• C. $n^3log^2n$
• D. $n^2log^2n$

Comments

First is O(n^2)

Second is O(n/logn)

Reason

log(n/logn) = log n - log(log n) = O (logn)

Again log (log ^2 n) = 2 * log(logn)

Now, log n > log (logn) asymptotically

So, n/logn > log ^2 n asymptotically

So, the answer is n^2 * n/logn = n^3 /logn

Answer 1

$f(n) = 2n^2 + nlogn$

$2n^2 > nlogn$

$f(n)\approx 2n^2$

 

$g(n) = n/logn + log^2n$

$n/logn > log^2n$

put $n = 2^{16}$

$n/logn = 2^{16} / log 2^{16} = 2^{16} / 2^4 = 2^{12}$

$log^2n = log^2 \ 2^{16} = loglog2^{16} = 4$

$g(n)\approx n/logn$

 

$f(n)*g(n) \approx 2n^3/logn$

$n^3/logn$