3

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?

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

1 Answers1

2

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.

Gaurang Tandon
  • 6,449
an4s
  • 3,716