0

If I have an algorithm with the running time $T(n) = 5n^4/100000 + n^3/100$, I know that I get Θ$(n^4)$.

Now, if I have something like $T(n) = \frac{10n^2 + 20n^4 + 100n^3}{n^4}$, does this yield Θ$(n^3)$?

I am trying to eliminate low-order terms to use the Substitution method to prove this.

Yiyuan Lee
  • 14,435
manthemanman
  • 1
  • The two results you mention are wrong. This seems to indicate a deep problem in your understanding of the no(ta)tion $\Theta$. – Did Mar 17 '14 at 07:30
  • Im sorry, Stack Exchange messed up the formatting of the first example. – manthemanman Mar 17 '14 at 07:34
  • My comment was applying to both versions of your question. The third version replaces $\Theta(n^3)$ by $\Theta(n^4)$ in the first example, hence now my comment applies only to the second example. Can you explain why you suggest $\Theta(n^3)$? (By the way, SE messed up nothing, you did, using LaTeX improperly.) – Did Mar 17 '14 at 07:37
  • actually, would it be Θ(1) since all members, except 20 (constant) will limit to zero when n is growing? – manthemanman Mar 17 '14 at 07:44
  • Yes. $ $ $ $ $ $ – Did Mar 17 '14 at 07:46

1 Answers1

1

In your second example you have $T(n) = \Theta(1)$ as $n\to +\infty$.

Emanuele Paolini
  • 21,447
  • What about mentioning that this assertion is resulting from the comments, which led the OP themselves to a solution? – Did Mar 17 '14 at 11:38