1

I have some issues in terms of the algebra I'm trying to solve for these 2 problems:

Check if f(n) = Θ(g(n))?

  • f (n) = 2log(n) vs. g(n) = n500
  • f (n) = (4 × n)150 + (2 × n + 500)400 and g(n) = 20 × n400 + (n + 500)200

So for the first function, I know that if I take the limit of f(n)/g(n) as n approaches infinity then it will approach 0 given g(n) grows much faster than f(n).

For the second function though, I tried by seeing if f(n) = O(n400) and f(n) = Ω(n400). I guess I'm just not understanding how to do that given the complexity of these functions. I think O(n400) is true but f(n) = Ω(n400) is not.

Thanks.

CD'A
  • 13
  • 3
  • For the second part, can you determine the highest power of $n$ in both $f(n)$ and $g(n)$? – an4s Sep 11 '20 at 18:23

1 Answers1

1

$f$ and $g$ in the second problem are polynomials, disguised as they might be, and the highest degrees are $400$ in both. It is these $n^{400}$ terms that eventually dominate as $n\to\infty$, so $\lim_{n\to\infty}\frac{f(n)}{g(n)}$ must tend to a positive constant. Hence $f(n)\in\Theta(g(n))$.

Parcly Taxel
  • 103,344
  • Right so that makes sense to me, however in the first problem, if I do the limit of f(n)/g(n) as n approaches infinity, wouldn't it approach a constant as well and not zero? But from what I read it should be 0 and not a constant. Or is that only because problem 2 has polynomials? – CD'A Sep 11 '20 at 18:33
  • @CDA Assuming $\log$ is binary (as is common in computing), $f(n)$ in the first problem is just $n$, so the ratio should go to zero. – Parcly Taxel Sep 11 '20 at 18:37