1
$\begingroup$

I'm currently studying growth of function chapter in Introduction to Algorithm. In exercise 3.1-2 the question is:

Show that for any real constants $a$ and $b$, where $b>0$,
$(n + a)^b = \Theta(n^b)$.

I understand I need to find constants $c_1$, $c_2$, $n_0 > 0$ where

$0 \leq c_1n^b \leq (n+a)^b \leq c_2n^b$ for all $n \geq n_0$.

But I don't understand what should I do after above step. Looking at the solution, it shows

$n + a \leq n + |a|$
$n + a \leq 2n$, when $|a| \leq n$

and

$n + a \geq n - |a|$
$n + a \geq \frac{n}{2}$ , when $|a| \leq \frac{n}{2}$

How did they come up with $n + a \leq n + |a|$ and $n + a \geq n - |a|$ just from $0 \leq c_1n^b \leq (n+a)^b \leq c_2n^b$ ? Are they derived from $0 \leq c_1n^b \leq (n+a)^b \leq c_2n^b$ ? Or are they just a general knowledge that can help solve this problem?

Please help me to understand them.

Thank you!

UPDATE: I have updated the question to be more specific.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ $(n+a)^b = n^b + c_1n^{b-1}a+... = \theta(n^b)$ $\endgroup$ – Mr. Sigma. Dec 19 '18 at 13:40
  • $\begingroup$ @Mr.Sigma.: $b$ can be any positive real number, say 0.5. $\endgroup$ – rici Dec 19 '18 at 13:54
  • $\begingroup$ O'Luck: $\mid a\mid$ is the absolute value of $a$; either $a$ or $-a$. If $a$ is positive, $n+ |a| = n + a$; otherwise $a$ is negative and $n+a < n < n + |a|$. What problem do you have with that? $\endgroup$ – rici Dec 19 '18 at 14:00
  • $\begingroup$ "Where did they get those inequalities?" Imagine that $n$ is very large. $\endgroup$ – John L. Dec 19 '18 at 14:12
  • $\begingroup$ Please do not post equations, text, and the like as images since these are incompatible with the site's search engine. Thank you. $\endgroup$ – dkaeae Dec 19 '18 at 14:20
1
$\begingroup$

I understand I need to find constants $c_1$, $c_2$, $n_0 > 0$ where

$0 \leq c_1n^b \leq (n+a)^b \leq c_2n^b$ for all $n \geq n_0$.

But I don't understand what should I do after above step.

The approach you would like to use here is "going backwards from the target".

Suppose we do have $c_1n^b \leq (n+a)^b$ for some constant $c_1\gt0$ when $n$ is large enough. What can we understand or deduce from it? What is needed to make it true?

Since the exponent is the same, we can use the law of same exponent, $(x/y)^m = x^m/y^m$ to simplify that inequality so that we will have the appearances of our variable $n$ closer to each other.

$$ c_1\leq \frac{(n+a)^b}{n^b}=\left(\frac{n+a}n\right)^b$$

Raising both sides to the power of $\frac1b$, we have

$$ (c_1)^{\frac1b}\leq \left(\frac{n+a}n\right)^{b\,\frac1b}=\frac{n+a}n = 1+\frac an$$

(Another way to obtain $(c_1)^{\frac1b}\leq\frac{n+a}n$ is to raise both sides of $c_1n^b \leq (n+a)^b$ to the power of $\frac 1b$.)

Since $c_1$ is a positive constant, $(c_1)^{\frac1b}$ is also a positive constant. To make the above inequality hold, we would like to make $\left|\frac an\right|$ small enough. For example, we can require $\left|\frac an\right|\le \frac12$. That is why you see the following condition.

$$|a|\le\frac12 n$$

What is nice here is that we can reverse the above argument to obtain a wanted constant $c_1$. Note that it is just as fine if we choose a different condition such as $|a|\le\frac13 n$ or $|a|\le\frac1{2019}n$ or infinitely many others.

If we start from $(n+a)^b \leq c_2n^b$, we could arrive at $|a|\le n$.

Are they derived from $0\le c_1n^b\le(n+a)^b\le c_2n^b$ ? Or are they just a general knowledge that can help solve this problem?

Yes, they are derived as you have just seen. You could say that they are general knowledge that helps solve this problem. You could also say that we just discovered some specific facts that help solve this problem.

Improve this answer
$\endgroup$
  • $\begingroup$ Wow thank you so much @apass-jack for your answer. This type of step-by-step answer is what I'm looking for. I guess I'm pretty weak at math. Before I accept your answer, I want to ask a few questions. In $(c_1)^{\frac1b}\leq \left(\frac{n+a}n\right)^{b\,\frac1b}=\frac{n+a}n = 1-\frac an$ , isn't it supposed to be $1+\frac an$ at the end? $\endgroup$ – O'Luck Dec 19 '18 at 23:12
  • $\begingroup$ Thanks for pointing out my typo. Updated. $\endgroup$ – John L. Dec 19 '18 at 23:35
  • $\begingroup$ Thank you. Next question is: "To make the above inequality hold, we would like to make $\left|\frac an\right|$ small enough". Why? If we choose big value for $\left|\frac an\right|$ , let say $\left|\frac an\right| > 1$ the inequality is still satisfied right? $\endgroup$ – O'Luck Dec 20 '18 at 0:01
  • $\begingroup$ Reason one: when $n$ goes to (positive) infinity, $|\frac an|$ goes to 0. So you cannot make it as big as you want. In fact, $|\frac an| \le |a|$ if we assume $n$ is a positive integer. Reason one is enough. Reason two: even if you could magically, suppose $a$ is negative, $\frac an$ is negative, too, which is bad for $1+\frac an$. $\endgroup$ – John L. Dec 20 '18 at 0:12
  • $\begingroup$ umm, I mean $|\frac an|$ as a whole not only the $n$. So, with $(c_1)^{\frac1b}\leq 1 + \frac an $ if $|\frac an| > 1 $ let say $|\frac an| = 2$ then $(c_1)^{\frac1b}\leq 1 + 2 $ , the inequation is still satisfied, am i right? $\endgroup$ – O'Luck Dec 20 '18 at 1:10
0
$\begingroup$

If n is large then we have n/2 ≤ n + a ≤ 2n.

We therefore have $(1/2)^b n^b ≤ n^b ≤ 2^b n^b$.

There you have your two constants: $(1/2)^b$ and $2^b$.

Improve this answer
$\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.