1
$\begingroup$

In the book I'm following I got the following solution:

To show that $(n + a)^b = \Theta(n^b)$, we want to find constants $c_1, c_2, n_0 > 0$ such that $$0 \leq c_1 n^b \leq (n + a)^b \leq c_2 n^b$$ for all $n \geq n_0$.

Note that $n + a \leq n + |a| \leq 2n$ when $|a| \leq n$, and $n + a \geq n − |a| \geq \frac{1}{2}n$ when $|a| \leq \frac{1}{2}n$.

Thus, when $n \geq 2 |a|$, $$0 \leq \frac{1}{2}n \leq n + a \leq 2n.$$

Since $b > 0$, the inequality still holds when all parts are raised to the power $b$: $$0 \leq \left(\frac{1}{2} n\right)^b \leq (n + a)^b \leq (2n)^b, \\ 0 \leq \left(\frac{1}{2}\right)^b n^b \leq (n + a)^b \leq 2^b n^b.$$

Thus, $c_1 = (1/2)^b$, $c_2 = 2^b$, and $n_0 = 2|a|$ satisfy the definition.

Can someone please elaborate how they got to this solution. What is the way to estimate Big Theta? I'm following Intro to Algorithms but it jumps so quickly and never really explains the math in calculating Big O, Big Theta and I'm really lost and scared that I might fail my exam. Can you point me to a good tutorial on how to find Big O step by step?

Thanks for your time I really appreciate your effort!

  • 1
    Please check that I formatted this properly as that wasn't straightforward and I want to make sure I didn't hose anything. Also, which book are you looking at? Regards2012-12-29
  • 0
    I'm following Introduction to Algorithms by Cormen..2012-12-29
  • 0
    that's what the book says :/ How did you get to that solution?2012-12-29

2 Answers 2