3.1-1 Let f(n) and g(n) be asymptotically non-negative functions. Using the basic definition of Θ-notation, prove that max(f(n),g(n))=Θ(f(n)+g(n)).
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 (f(n) + g(n)) \le \max(f(n), g(n)) \le c_2 (f(n) + g(n))$$ for all $$n \ge n_0$$. As the functions are asymptotically non-negative, we can assume that for some $$n_0 > 0, f(n) \ge 0$$ and $$g(n) \ge 0$$.
So Far
$$n \ge n_0$$ , $$f(n) + g(n) \ge \max(f(n), g(n))$$
Also note that,
$$f(n) \le \max(f(n), g(n))$$
and $$g(n) \le \max(f(n), g(n)) \\
\therefore f(n) + g(n) \le 2 \max(f(n), g(n)) \\
\Rightarrow \frac 1 2 (f(n) + g(n)) \le \max(f(n), g(n))$$
Therefore, we can combine the above two inequalities as follows:
$$0 \le \frac 1 2 (f(n) + g(n)) \le \max(f(n), g(n)) \le (f(n) + g(n)) \text { for } n \ge n_0$$
So, $$\max(f(n), g(n)) = \Theta(f(n) + g(n))$$ because there exists $$c_1 = \frac 1 2$$ and $$c_2 = 1$$
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 (f(n) + g(n)) \le \max(f(n), g(n)) \le c_2 (f(n) + g(n))$$ for all $$n \ge n_0$$. As the functions are asymptotically non-negative, we can assume that for some $$n_0 > 0, f(n) \ge 0$$ and $$g(n) \ge 0$$.
So Far
$$n \ge n_0$$ , $$f(n) + g(n) \ge \max(f(n), g(n))$$
Also note that,
$$f(n) \le \max(f(n), g(n))$$
and $$g(n) \le \max(f(n), g(n)) \\
\therefore f(n) + g(n) \le 2 \max(f(n), g(n)) \\
\Rightarrow \frac 1 2 (f(n) + g(n)) \le \max(f(n), g(n))$$
Therefore, we can combine the above two inequalities as follows:
$$0 \le \frac 1 2 (f(n) + g(n)) \le \max(f(n), g(n)) \le (f(n) + g(n)) \text { for } n \ge n_0$$
So, $$\max(f(n), g(n)) = \Theta(f(n) + g(n))$$ because there exists $$c_1 = \frac 1 2$$ and $$c_2 = 1$$
No comments:
Post a Comment