# Which one is asymptotically larger? $100n+\log n$ Or $n+(\log n)^2$

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?

• Do you know the definition of $f = \Theta(g)$? – Robert Z Jun 10 '18 at 7:46
• 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 – Brij Raj Kishore Jun 10 '18 at 7:49
• I mean a formal definition (the one which is useful here). – Robert Z Jun 10 '18 at 7:52
• 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)$ – Brij Raj Kishore Jun 10 '18 at 8:01

## 1 Answer

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.