2
$\begingroup$

I understand how I would do this if the problem were as such

$8n + 5$ is $O(n)$

$c>0$ and an integer constant $n(not 0) \geq 1$ such that $8n + 5 \leq cn$ for every integer $n \geq n(not 0)$

we could let $c= 13$ and $n(not 0) = 1$

or we could let $c = 9$ and $n( not 0) = 5$.

I'm just not sure how to go about $6n^2 +12n$

$\endgroup$
1
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – FrankW
    Commented Oct 7, 2014 at 4:16

1 Answer 1

2
$\begingroup$

Let $f(n)=6n^2 + 12n$

The $O$ notation for $f(n)$ can be derived from the following simplification rules:

  1. If $f(n)$ is a sum of several terms, we keep only the one with largest growth rate.
  2. If $f(n)$ is a product of several factors, any constant is omitted.

From rule 1, $f(n)$ is a sum of two terms, the one with largest growth rate is the one with the largest exponent as a function of $n$, that is: $6n^2$

From rule 2, $6$ is a constant in $6n^2$ because it does not depend on $n$, so it is omitted.

Then: $f(n)$ is $O(n^2)$

$\endgroup$
3
  • $\begingroup$ Thanks, how could I change that to justify that it is big omega or big theta? $\endgroup$
    – Frightlin
    Commented Oct 7, 2014 at 5:07
  • $\begingroup$ @Frightlin Rules 1 and 2 apply equally well to $\Omega$ and $\Theta$ notations. Note that $f \in \Omega(g)$ if and only if $g \in O(f)$, and $f \in \Theta(g)$ if and only if $f \in O(g)$ and $f \in \Omega(g)$. $\endgroup$
    – Patrick87
    Commented Oct 7, 2014 at 5:21
  • $\begingroup$ @Frightlin These "rules" always yield $\Theta$. $\endgroup$
    – Raphael
    Commented Oct 7, 2014 at 6:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.