In the book Algorithms by Sanjoy Dasgupta in 1st chapter exercise

Q.1. In each of the following situation, indicate whether $f = \mathcal{O}(g)$ , or $f = \Omega(g) $, or both (in which case $ f = \Theta(g) $

(c) $f(n) = 100 n + \log\,n $ , $g(n) = n + (\log\, n)^2$

I have plotted it in Desmos. I have no idea why $f(n)$ is growing faster even though $g(n)$ has square in it. I might be wrong. Please explain which one is larger and why?

  • $\begingroup$ Do you know the definition of $f = \Theta(g)$? $\endgroup$ – Robert Z Jun 10 '18 at 7:46
  • $\begingroup$ I think I am. Roughly if it is tight bounded or here if $f(n)$ and $g(n)$ are comparable or in other words if best case and worst case is of same complexity. Correct me if I am wrong $\endgroup$ – Brij Raj Kishore Jun 10 '18 at 7:49
  • $\begingroup$ I mean a formal definition (the one which is useful here). $\endgroup$ – Robert Z Jun 10 '18 at 7:52
  • $\begingroup$ I think no. Because in book they have given definition of $\mathcal{O}$ notation and I got it and they move forward by saying $f = \Omega (g) $ means $ g = \mathcal{O} (f) $ and finally they say $f = \Theta (g) $ means $ f = \mathcal{O} (g) $ and $f = \Omega (g) $ $\endgroup$ – Brij Raj Kishore Jun 10 '18 at 8:01

Hint: $f(n)$ is $\mathcal O(g(n))$ if $\exists c\ge0$ s.t. $\displaystyle\lim_{n\to\infty}\dfrac{f(n)}{g(n)} = c$.

From Wolfram Alpha, $\displaystyle\lim_{n\to\infty}\dfrac{f(n)}{g(n)} = \lim_{n\to\infty}\dfrac{100n + \log n}{n + \log^2n} = 100$. Therefore, $f(n)$ is $\mathcal O(g(n))$.

As a practice, try to solve the limit (using L'Hospital's Rule) yourself and see whether the limit does, in fact, result in a constant.

Also, this might be helpful.


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.