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$$
$$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$$
No comments:
Post a Comment