When simple gets complex

As i was topic hopping on a lazy day, i stumbled upon this seemingly simple exercise (3.1-2) from chapter 3 of "Introduction to Algorithms" -CLRS

What makes me write about this is the actual amount of time i spent, trying to formally prove it to myself :-)

And of course, after having my rather long proof, i thought there must be a much more elegant one.

Well, before reading further, i recommend you to try the proof yourself or recollect it if done already, for there is a good chance yours is that 'everyone can understand in 2 simple steps' kind of a proof 👍

What you need to prove is that there exist positive constants $c_1$, $c_2$, and $n_0$ such that:

\(c_1 * n^b \leq (n+a)^b \leq c_2 * n^b\)      \(\forall{n} > n_0 \) where $a,b \in \mathbb{R}$ and b > 0

Which is tersely represented as " \( (n+a)^b = \Theta (n^b) \)" in algorithm analysis literature

  _______
 /  12   \
 |    |    |
 |9   |   3|
 |     \   |
 |         |
 \___6___/

Enough time has passed, and i guess you have your proof ready. Be ready to have some fun now looking at what follows as a proof below 😛

Part I -- $\Omega$

Lets begin by the assumption $c * n^b \le (n+a)^b$ where '$c$' is not really a constant, but a suitable variable for each possible $n$.

                => $c \le ((n+a)/n)^b$

If $a \gt 0$, $c_1=1$ readily makes $n^b < (n+a)^b$

But, if $a \lt 0$, such that $|a|=d$, then we have $c*n^b \le (n-d)^b$:

=> $c \le ((n-d)/n)^b$

for $c $ to be $\gt 0$, $n$ has to be greater than $d$, and we have:

 $c \in  \{ 1/(d+1)^b, $

             $(2/(d+2))^b,$

             $(3/(d+3))^b,$

             $ .. $

        $ \}$

 $\forall{n} \in \{d+1, d+2, d+3, .... \}$

If $c$ is an ascending series, we can safely take the lowest value in the progression for the constant.
If $c$ is a descending series, then as you may have guessed, we would never be able to find a $c_1 \in c$ small enough to make the (in)equation $c_1*n^b \le (n+a)^b$ hold for arbitrarily large $n$.
Note that there can be other functions which are not purely ascending or descending, but luckily the one we are dealing with right now is. Why? Because in our $i{th}$ term $(i/(i+d))^b$ there is no component which can change sign as $i$ increases from $1$ to any arbitrarily large value.

So lets spell out the $i^{th}$ and $i+1^{th}$ term of $c$
$c_i = (i/(i+d))^b$ and $c_{i+1} = ((i+1)/(i+1+d))^b$

If we ignore the exponent and look at the difference in base values of $i^{th}$ and $i+1^{th}$ element, we have

$\Delta_{i,i+1} = (i+1)/(i+1+d) - i/(i+d)$

 $= ((i+1)(i+d) - i(i+1+d))/(i+d)(i+1+d)$

Ignoring the denominator, we have the numerator as:
$ \require{cancel} \cancel{i^2 + {i*d} + i} + d - \cancel{(i^2 + {i*d} + i)} = d$ which is positive.
Hence $1/(d+1)^b$ is going to be less than other terms.
And thus if we choose $c_1$ as $1/(|a|+1)^b$, we have $c_1*n^b \le (n+a)^b$ $\forall n \gt |a|$

So, $(n+a)^b = \Omega(n^b)$

Part II -- Big-Oh 
 Now lets consider
$(n+a)^b \le c_2 * n^b$  => $c_2*n^b \gt (n+a)^b$ => $c2 \ge ((n+a)/n)^b$

When $a \lt 0$, the fraction $(n+a)/n$ would be less than one and hence $c_2 = 1$ would suffice.
But, when $a \gt 0$, the fraction $(n+a)/n > 2$ $\forall{n} < a$, and $(n+a)/n < 2$ $\forall{n} > a$
The above observation is intuitive, and also not too difficult to prove formally.
If n < a, $a$ can be expressed as $a = n + x$ where $x \gt 0$.
     => $(n+a)/n =$
                     $(n+n+x)/n = 2n/n + x/n =$
                             $2 + x/n$
Since x/n is positive, we have $(n+a)/n > 2$
If n > a, then $n$ can be expressed as $n = a + x$ where $x \gt 0$.
     => $(n+a)/n =$
                     $(a+a+x)/(a+x) = $
                             $a/(a+x) + 1$
Since $a/(a+x)$ will always be less than 1, we have $(n+a)/n < 2$

Hence for $c_2 = 2^b$ and $n0  = |a| + 1$ we have $(n+a)^b < c2 * n^b$

=> $(n+a)^b = O(n^b)$

Part III -- $\Theta$
from I and II we have:

 $(n+a)^b = \Theta(n^b)$ with $c_1 = (1/(|a|+1))^b; c_2 = 2^b;n_0=|a|+1$

Refinement
in Part II the value we chose for $n_0$ made it such that the constant $a$ was not part of the equation for constant $c_2$.
Can we do something similar for Part I as well? Ofcourse, yes! We had $c \le ((n-d)/n)^b)$ where $d=|a|$
Why not make $n_0 = 2*d$, then we have $c \le (1/2)^b$
Plus from Part I's generic analysis we know that $((n-d)/n)^b$ is an increasing series of numbers.
So, the simpler choices would then be $n_0 = 2 * |a|$ and $c_1 = (1/2)^b$

However, we still have some constants from the earlier inelegant Part-I that can be helpful if $a$ is a pretty big negative number 😉

Summary
As an after thought i don't regret this proof so much but understand the importance of elegance and simplification even more better than before. Hope you did so too 😃
Now try to prove the way you have been mutliplying multi-digit numbers since primary school is actually correct.