3.4 MANIPULATING BIG-O

3.4 MANIPULATING BIG-O

171. Prove that if $f_i(n) = O(g_1(n))$ and $f_2(n) = O(g_2(n))$, then $f_1(n) + f_2(n) = O(g_1(n)+g_2(n))$.

$$
\begin{aligned}
f_1(n) &\leq c_1 \cdot g_1(n)
\\
f_2(n) &\leq c_2 \cdot g_2(n)
\\
\end{aligned}
$$
일 때

$$
\begin{aligned}
f_1(n) + f_2(n) = O(g_1(n)+g_2(n))
\\
f_1(n) + f_2(n) \leq c(g_1(n)+g_2(n))
\end{aligned}
$$
를 증명하자

$$
\begin{aligned}
f_1(n) + f_2(n) &\leq c_1 \cdot g_1(n) + c_2 \cdot g_2(n)
\\
Max(c_1,c_2) &= c_0
\\
f_1(n) + f_2(n) &\leq c_0 \cdot g_1(n) + c_0 \cdot g_2(n)
\\
&\leq c_0 (g_1(n) + g_2(n))
\end{aligned}
$$

이므로 c 가 $c_0$일때 $n>=n_0$ 인 모든 n에 대해서 성립한다.

172. Prove that if $f_i(n) = \Omega(g_1(n))$ and $f_2(n) = \Omega(g_2(n))$, then $f_1(n) + f_2(n) = \Omega(g_1(n)+g_2(n))$.

$$
\begin{aligned}
f_1(n) &\geq c_1 \cdot g_1(n)
\\
f_2(n) &\geq c_2 \cdot g_2(n)
\\
\end{aligned}
$$
일 때

$$
\begin{aligned}
f_1(n) + f_2(n) = \Omega(g_1(n)+g_2(n))
\\
f_1(n) + f_2(n) \geq c(g_1(n)+g_2(n))
\end{aligned}
$$
를 증명하자

$$
\begin{aligned}
f_1(n) + f_2(n) &\geq c_1 \cdot g_1(n) + c_2 \cdot g_2(n)
\\
Min(c_1,c_2) &= c_0
\\
f_1(n) + f_2(n) &\geq c_0 \cdot g_1(n) + c_0 \cdot g_2(n)
\\
&\geq c_0 (g_1(n) + g_2(n))
\end{aligned}
$$

이므로 c 가 $c_0$일때 $n>=n_0$ 인 모든 n에 대해서 성립한다.

173. Prove that if $f_i(n) = O(g_1(n))$ and $f_2(n) = O(g_2(n))$, then $f_1(n) + f_2(n) = O(max(g_1(n),g_2(n)))$.

$$
\begin{aligned}
f_1(n) &\leq c_1 \cdot g_1(n)
\\
f_2(n) &\leq c_2 \cdot g_2(n)
\\
\end{aligned}
$$
일 때

$$
\begin{aligned}
f_1(n) + f_2(n) \leq c\cdot max(g_1(n),g_2(n))
\end{aligned}
$$
를 증명하자

$$
\begin{aligned}
f_1(n) + f_2(n) &\leq c_1 \cdot g_1(n) + c_2 \cdot g_2(n)
\\
a+b&\leq 2 \cdot max(a,b)
\\
&\text{171 을 이용하여}
\\
f_1(n) + f_2(n) &\leq c_0 \cdot g_1(n) + c_0 \cdot g_2(n)
\\
&\leq c_0 (g_1(n) + g_2(n))
\\
c_0 (g_1(n) + g_2(n)) &\leq c \cdot max(g_1(n),g_2(n))
\end{aligned}
$$

이므로 c 가 $2 \cdot c_0$일때 $n>=n_0$ 인 모든 n에 대해서 성립한다.

174. Prove that if $f_i(n) = \Omega(g_1(n))$ and $f_2(n) = \Omega(g_2(n))$, then $f_1(n) + f_2(n) = \Omega(min(g_1(n),g_2(n)))$.

$$
\begin{aligned}
f_1(n) &\geq c_1 \cdot g_1(n)
\\
f_2(n) &\geq c_2 \cdot g_2(n)
\\
\end{aligned}
$$
일 때

$$
\begin{aligned}
f_1(n) + f_2(n) \geq c\cdot min(g_1(n),g_2(n))
\end{aligned}
$$
를 증명하자

$$
\begin{aligned}
f_1(n) + f_2(n) &\geq c_1 \cdot g_1(n) + c_2 \cdot g_2(n)
\\
a+b&\geq 2 \cdot min(a,b)
\\
&\text{172 를 이용하여}
\\
f_1(n) + f_2(n) &\geq c_0 \cdot g_1(n) + c_0 \cdot g_2(n)
\\
&\geq c_0 (g_1(n) + g_2(n))
\\
c_0 (g_1(n) + g_2(n)) &\geq c \cdot min(g_1(n),g_2(n))
\end{aligned}
$$

이므로 c 가 $1/2 \cdot c_0$일때 $n>=n_0$ 인 모든 n에 대해서 성립한다.

175. Suppose that $f_1(n) = \Theta(g_1(n))$ and $f_2(n) = \Theta(g_2(n))$. Is it true that $f_1(n) + f_2(n) = \Theta(g_1(n) + g_2(n))$? Is it true that $f_1(n) + f_2(n) = \Theta(max(g_1(n),g_2(n))$? Is it true that $f_1(n) + f_2(n) = \Theta(min(g_1(n),g_2(n))$? Justify your answer.

$$
\begin{aligned}
d_1 \cdot g_1(n) \leq f_1(n) &\leq c_1 \cdot g_1(n)
\\
d_2 \cdot g_2(n) \leq f_2(n) &\leq c_2 \cdot g_2(n)
\\
\end{aligned}
$$
일 때

$$
\begin{aligned}
d_3 \cdot (g_1(n) + g_2(n)) &\leq f_1(n) + f_2(n) \leq c_3\cdot (g_1(n)+g_2(n)) \text{\quad and}
\\
d_4 \cdot max(g_1(n),g_2(n) &\leq f_1(n) + f_2(n) \leq c_4\cdot max(g_1(n),g_2(n)) \text{\quad and}
\\
d_5 \cdot min(g_1(n),g_2(n) &\leq f_1(n) + f_2(n) \leq c_5\cdot min(g_1(n),g_2(n))
\end{aligned}
$$
를 증명하자

1. $d_3 \cdot (g_1(n) + g_2(n)) \leq f_1(n) + f_2(n) \leq c_3\cdot (g_1(n)+g_2(n))$

$$
\begin{aligned}
d_1 \cdot g_1(n)+d_2 \cdot g_2(n) &\leq f_1(n) +f_2(n)\leq c_1 \cdot g_1(n)+c_2 \cdot g_2(n)
\\
min(a_1,a_2)(b_1+b_2) &\leq a_1\cdot b_1 + a_2\cdot b_2 \leq max(a_1,a_2)(b_1+b_2)
\\
min(d_1,d_2) &= d_0
\\
max(c_1,c_2) &= c_0
\\
d_0 \cdot (g_1(n)+g_2(n)) &\leq f_1(n) +f_2(n)\leq c_0 \cdot ( g_1(n)+ g_2(n))
\\
\end{aligned}
$$

d가 $d_0$ 이고 c가 $c_0$ 일때 성립한다.

2. $d_4 \cdot max(g_1(n),g_2(n)) \leq f_1(n) + f_2(n) \leq c_4\cdot max(g_1(n),g_2(n))$

$$
\begin{aligned}
d_0 \cdot (g_1(n)+g_2(n)) &\leq f_1(n) +f_2(n)\leq c_0 \cdot (g_1(n)+ g_2(n))
\\
a+b &\leq 2 \cdot max(a,b)
\\
d_0 \cdot (g_1(n)+g_2(n))\leq 2\cdot d_0 \cdot max(g_1(n),g_2(n)) &\leq f_1(n) +f_2(n)\leq c_0 \cdot (g_1(n)+ g_2(n)) \leq 2\cdot c_0 \cdot max(g_1(n),g_2(n))
\end{aligned}
$$
$2 \cdot d_0 = c_0$ 일 때 성립

min 도 동일

176. Prove that if $f_i(n) = O(g_1(n))$ and $f_2(n) = O(g_2(n))$, then $f_1(n) \cdot f_2(n) = O(g_1(n)\cdot g_2(n))$.

$$
\begin{aligned}
0\leq f_1(n) &\leq c_1 \cdot g_1(n)
\\
0\leq f_2(n) &\leq c_2 \cdot g_2(n)
\\
\end{aligned}
$$
일 때

$$
\begin{aligned}
0\leq f_1(n) \cdot f_2(n) \leq c\cdot (g_1(n) \cdot g_2(n))
\end{aligned}
$$
를 증명하자

$$
\begin{aligned}
0\leq f_1(n) \cdot f_2(n) &\leq c_1 \cdot g_1(n) \cdot c_2 \cdot g_2(n)
\\
0\leq f_1(n) \cdot f_2(n) &\leq c_1 \cdot c_2 \cdot g_1(n) \cdot g_2(n)
\\
\end{aligned}
$$

이므로 c 가 $c_1 \cdot c_2$ 인 모든 n에 대해서 성립한다.

177. Prove that if $f_i(n) = \Omega(g_1(n))$ and $f_2(n) = \Omega(g_2(n))$, then $f_1(n) \cdot f_2(n) = \Omega(g_1(n)\cdot g_2(n))$.

$$
\begin{aligned}
0\leq c_1 \cdot g_1(n) &\leq f_1(n)
\\
0\leq c_2 \cdot g_2(n) &\leq f_2(n)
\\
\end{aligned}
$$
일 때

$$
\begin{aligned}
0\leq c\cdot (g_1(n) \cdot g_2(n)) \leq f_1(n) \cdot f_2(n)
\end{aligned}
$$
를 증명하자

$$
\begin{aligned}
0\leq f_1(n) \cdot f_2(n) &\leq c_1 \cdot g_1(n) \cdot c_2 \cdot g_2(n)
\\
0\leq c_1 \cdot c_2 \cdot g_1(n) \cdot g_2(n) &\leq f_1(n) \cdot f_2(n)
\\
\end{aligned}
$$

이므로 c 가 $c_1 \cdot c_2$ 인 모든 n에 대해서 성립한다.

183. Show that big-O is transitive. That is, if $f(n) = O(g(n))$ and $g(n) = O(h(n))$, then $f(n) = O(h(n))$.

$$
\begin{aligned}
0\leq f(n) &\leq c_1 \cdot g(n)
\\
0\leq g(n) &\leq c_2 \cdot h(n)
\\
\end{aligned}
$$
일 때

$$
\begin{aligned}
f(n) \leq c \cdot h(n)
\end{aligned}
$$
임을 증명하자

$$
\begin{aligned}
f(n) &\leq c_1 \cdot g(n)
\\
&\leq c_1 \cdot (c_2 \cdot h(n))
\\
\end{aligned}
$$

$c_1 \cdot c_2$가 c일 때 성립한다.

184. Prove that if $f(n) = O(g(n))$, then $f(n)^k = O(g(n)^k)$.

$$
\begin{aligned}
0\leq f(n) &\leq c_1 \cdot g(n)
\end{aligned}
$$
일 때

$$
\begin{aligned}
f(n)^k &\leq c \cdot g(n)^k
\end{aligned}
$$
임을 증명하자

$$
\begin{aligned}
f(n) &\leq c_1 \cdot g(n)
\\
f(n) &\leq c_1 \cdot g(n)
\\
...
\\
f(n) &\leq c_1 \cdot g(n) \quad \text{k번 곱한다.}
\\
\\
f(n)^k &\leq c_1^k \cdot g(n)^k
\end{aligned}
$$

$c_1^k$가 c일 때 성립한다.

184. Prove or disprove: If $f(n) = O(g(n))$, then $2^{f(n)} = O(2^{g(n)})$

$$
\begin{aligned}
f(n) &= 2\log n
\\
g(n) &= \log n
\\
f(n) &\leq c \cdot g(n)
\\
2^{f(n)} &\nleq 2^{g(n)}
\\
2^{2\log n} &\nleq 2^{\log n}
\\
n^2 &\nleq n
\end{aligned}
$$

186. Prove or disprove: If $f(n) = O(g(n))$, then $\log f(n) = O(\log g(n))$

$$
\begin{aligned}
0\leq f(n) &\leq c_1 \cdot g(n)
\end{aligned}
$$
일 때

$$
\begin{aligned}
\log f(n) \leq c \cdot \log g(n)
\end{aligned}
$$
임을 증명하자

양 변에 2를 밑으로 하는 로그를 취하자.

로그 함수는 단조 증가이므로 성립한다.
$$
\begin{aligned}
\log f(n) &\leq \log c_1 \cdot g(n)
\\
\log f(n) &\leq \log c_1 + \log g(n)
\end{aligned}
$$

여기서 g(n) 이 1이고 f(n) 이 2라면

$\log g(n) = 0$이므로 성립하지 않는다.

187. Suppose $f(n) = \Theta(g(n))$. Prove that $h(n) = O(f(n))$ iff $h(n) = O(g(n))$

$$
\begin{aligned}
d_1 \cdot g(n)\leq f(n) &\leq c_1 \cdot g(n)
\end{aligned}
$$
일 때

$$
\begin{aligned}
h(n) = O(f(n)) \quad iff \quad h(n) = O(g(n))
\end{aligned}
$$
임을 증명하자

187-1.

$$
\begin{aligned}
h(n) &\leq c_2\cdot f(n) \quad \text{라고 가정했을 때}
\\
h(n) &\leq c \cdot g(n) \quad \text{를 증명하자}
\\
\end{aligned}
$$

$$
\begin{aligned}
f(n) &\leq c_1 \cdot g(n)
\\
h(n) &\leq c_2 \cdot f(n) \leq c_2 \cdot c_1 \cdot g(n)
\end{aligned}
$$

$c_2 \cdot c_1$ = c 일 때 성립

187-2.

$$
\begin{aligned}
h(n) &\leq c_2 \cdot g(n) \quad \text{라고 가정했을 때}
\\
h(n) &\leq c\cdot f(n) \quad \text{를 증명하자}
\\
\end{aligned}
$$

$$
\begin{aligned}
d_1 \cdot g(n) &\leq f(n)
\\
c_2 \cdot g(n) &\leq (c_2/d_1) \cdot f(n)
\\
h(n) \leq c_2 \cdot g(n) &\leq (c_2/d_1) \cdot f(n)
\\
\end{aligned}
$$

$(c_2/d_1)$ = c 일 때 성립

188 Prove or disprove: If $f(n) = O(g(n))$, then $f(n)/h(n) = O(g(n)/h(n))$

$$
\begin{aligned}
f(n) &\leq c_1 \cdot g(n)
\end{aligned}
$$
일 때

$$
\begin{aligned}
f(n)/h(n) &\leq c \cdot g(n)/h(n)
\\
h(n) < 0 라면 성립하지 않는다.
\end{aligned}
$$