Chapter 3 Exercise 3.1-3, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

3.1-3 Explain why the statement, “The running time of algorithm A is at $$O(n^2)$$  ,” is meaningless.

Solution: Let us assume the running time of the algorithm is T(n). Now, by definition, O-notation gives an upper bound for growth of functions but it doesn’t specifies the order of growth. Therefore, saying $$T(n) \ge O(n^2)$$ means growth of T(n) is greater than some upper bound which is meaningless as we do not have any idea about what we are comparing it with.

For example, $$f(n) = 0$$ is $$O(n^2)$$ for all n. So, $$T(n) \ge f(n)$$   doesn’t tell us anything new as all running times are non-negative.

Chapter 3 Exercise 3.1-2, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

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

Solution:
To prove this, we have to show that there exists constants $$c_1, c_2, n_0 > 0$$ such that $$0 \le c_1 n^b \le (n + a)^b \le c_2 n^b$$   for all $$n \ge n_0$$
Note that, $$n + a \le 2n ,$$ when $$|a| \le n$$ Also note, $$n + a \ge \frac 1 2 n ,$$ when $$|a| \le \frac n 2$$  
Therefore, when $$n \ge 2 \vert a \vert ,$$ $$0 \le \frac n 2 \le n + a \le 2n$$
As b>0, we can raise all the terms of the previous inequality to the power of b without breaking the inequality:
$$\begin {align} 0 \le (\frac n 2)^b & \le (n + a)^b \le (2n)^b \\ \Rightarrow 0 \le \frac 1 {2^b}n^b & \le (n + a)^b \le 2^bn^b \end {align}$$
So, $$(n + a)^b = \Theta(n^b)$$ because there exists $$c_1 = 1/{2^b},c_2 = 2^b ,$$ and  $$n_0 = 2 \vert a \vert$$