This problem is from "Introduction to Algorithms" Cormen 3rd edition. It's problem 3.1-2 from the book. I have ready many many websites, including this one, on how to solve this problem. My motivation is that I'm a grad student and taking "Introduction to Algorithms". I don't know how to solve this problem in a way that makes sense to me. I could loosely copy some elses work and hopefully not get docked on grading, but I want to get a doctorate in computer science after my master's degree. I'm not cutting corners, taking less classes to get straight A's and thoroughly understand everything in all my classes.
Here is the problem: Show that for any real constants a and b, where b>0, (n + a)^b = θ(n^b)
The way to set it up is using the definition of theta asymptotic notation, which is: θ(g(n)) = {f(n): there exists positive constants c1, c2 and n0 such that
0 <= c1g(n) <= f(n) <= c2g(n) for all n >= n0}.
So initially setting up the inequality is:
0 <= c1*(n^b) <= (n + a)^b <= c2*(n^b)
I don't know how to get from this point to the answer, which is c1=(1/2) and c2=2. I already have seen the answers to the first six pages that come up on Google by typing in the problem question. One of them was from this website. I thoroughly read all the solutions and some are done a lot different (or seem that way on the surface).
I need a detailed explanation. Here is an example. Changing (n+a) to (n + |a|). Why use the absolute value? Because a negative value is possible for a when n > 0? Why? Show examples. Explain each step in depth. I don't remember everything from every math class I took. I did read the appendices for the Algorithms book and read chapter 3 all the way through. So, yes I did study how to manipulate equations recently. I did my part and still don't know how to solve this problem all the way through making sense the entire way and can defend each step cogently.
Can anyone help?
Best Answer
\begin{align*} (n + a)^b ≤ (n + |a|)^b & \text{ where } n > 0\\ ≤ (n + n)^b & \text{ for } n ≥ |a|\\ = (2n)^b\\ = c1 · n^b & \text{ where } c1 = 2^b \end{align*}
Thus \begin{align*} (n + a)^b = Ω(n^b)\\ (n + a)^b ≥ (n − |a|) b& \text{ where } n > 0\\ ≥ (c′_2n)^b & \text{ for } c′_2 = 1/2 \text{ where }n ≥ 2|a|\\ \end{align*} as $n/2 ≤ n − |a|$, for $n ≥ 2|a|$.
Thus $$(n + a)^b = \Omega(n^b)$$
The result follows from 1 and 2 with $c_1 = 2^b$, $c_2 = 2^{−b}$, and $n_0 ≥ 2|a|$.