1
$\begingroup$

The question is,

Prove that $\frac{n^2}{2} - 3n = \Theta(n^2)$.

I understand that to do this I must determine positive constants $c_1$, $c_2$, and $n_0$ such that $$c_1n^2 \leq \frac{n^2}{2} - 3n \leq c_2n^2$$

I simplified by dividing by $n^2$ which left

$$c_1 \leq \frac{1}{2} - \frac{3}{n} \leq c_2$$

The book I am following along with says "We can make the right-hand inequality hold for any value of $n \geq 1$ by choosing any constant $c_2 \geq \frac{1}{2}$. Likewise, we can make the left-hand inequality hold for any value of $n \geq 7$ by choosing any constant $c_1 \leq \frac{1}{14}$."

I understand that there are other choices for the constants but I'm not sure of a method for determining them. What general procedure should I use for determining these other than guess and check?

$\endgroup$
  • $\begingroup$ For polynomials, determining an upper constant can be done by ignoring all negative terms and increasing the order of all positive terms to match the highest ordered term. For example $10n^5-2n^4-3n^3+n^2+5n \leq 10n^5+n^2+5n\leq 10n^5+n^5+5n^5\leq 16n^5$. Finding lower bounds takes a bit more effort to explain but a similar approach can sometimes work. $\endgroup$ – JMoravitz Sep 4 '16 at 22:02
1
$\begingroup$

What you did so far was good. Then, to determine an exact choice for the constants $c_1$ and $c_2$, you should think carefully about the expression, in this case $$ \frac{1}{2} - \frac{3}{n}. $$ As $n$ gets larger, what does this sequence do? Well, it gets closer and closer to $\frac12$. And it only increases; it gets closer to $\frac12$ from below.

That means we can pick the upper bound $c_2 = \frac12$. And since it increases, we can pick the lower bound $c_1$ to be the $n$th term for some suitably large $n$. In the book, they picked $n = 7$ to get $\frac{1}{2} - \frac{3}{7} = \frac{1}{14}$ as the lower bound.

$\endgroup$
1
$\begingroup$

Your task doesn't really require you to specify the constants. One approach for the solution would be to state that the sequence $$ \frac{1}{2} - \frac{3}{n} $$ converges to the constant $ \frac{1}{2} $. This means that for any $ \varepsilon > 0 $ there exists $ N(\varepsilon)$ such that $ \frac{1}{2} - \varepsilon < \frac{1}{2} - \frac{3}{n} < \frac{1}{2} + \varepsilon $ for $n > N(\varepsilon) $, which gives you the two constans for all sufficiently large $ n $ (i.e. larger than $ N(\varepsilon) $)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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