3.1 RANK THE FUNCTIONS

98 Consider the following eighteen functions:


$\sqrt{n}$	$n$	$2^n$
$n\log n$	$n-n^3+7n^5$	$n^2+\log n$
$n^2$	$n^3$	$\log n$
$n^{1/3}+\log n$	$(\log n)^2$	$n!$
$\ln n$	$n/\log n$	$\log \log n$
$(1/3)^n$	$(3/2)^n$	$6$

Group these functions so that f(n) and g(n) are in the same group if and only if f(n) = O(g(n)) and f(n) = O(f(n)), and list the groups in increasing order.

1. Θ관계 끼리 묶기

$\sqrt{n}$

$n$

$2^n$

$n\log n$

$n-n^3+7n^5$

${n^2 + \log n,,n^2}$

$n^3$

${\log n,,\ln n}$

$n^{1/3}+\log n$

$(\log n)^2$

$n!$

$n/\log n$

$\log \log n$

$(1/3)^n$

$(3/2)^n$

2. 그룹을 증가 순서대로 정렬

$$
\begin{aligned}
(1/3)^n
\\
\log \log n
\\
{\log n,,\ln n}
\\
(\log n)^2
\\
n^{1/3}+\log n
\\
\sqrt{n}
\\
n/\log n
\\
n
\\
n\log n
\\
{n^2 + \log n,,n^2}
\\
n^3
\\
n-n^3+7n^5
\\
(3/2)^n
\\
2^n
\\
n!
\end{aligned}
$$

틀릴 수도 있습니다..

99 Draw a line from each of the five functions in the center to the best big-Ω value on the left, and the best big-O value on the right


$\Omega(1/n)$		$O(1/n)$
$\Omega(1)$		$O(1)$
$\Omega(\log \log n)$		$O(\log \log n)$
$\Omega(\log n)$		$O(\log n)$
$\Omega(log^2 n)$		$O(log^2 n)$
$\Omega(\sqrt[3]{n})$		$O(\sqrt[3]{n})$
$\Omega(n/\log n)$	$1/(\log n)$	$O(n/\log n)$
$\Omega(n)$	$7n^5-3n+2$	$O(n)$
$\Omega(n^{1.00001})$	$(n^2+n)/(\log^2n+\log n)$	$O(n^{1.00001})$
$\Omega(n^{3/2})$	$2^{\log^2n}$	$O(n^{3/2})$
$\Omega(n^2/\log^2 n)$	$3^n$	$O(n^2/\log^2 n)$
$\Omega(n^2/\log n)$		$O(n^2/\log n)$
$\Omega(n^2)$		$O(n^2)$
$\Omega(2^n)$		$O(2^n)$
$\Omega(5^n)$		$O(5^n)$
$\Omega(n^n)$		$O(n^n)$
$\Omega(n^{n^2})$		$O(n^{n^2})$

99-1. $1/(\log n)$

분모 부분을 보면 $\log n$ 이다.

이는 n 보다 작고, 1보다 크다. -> 분모니까 반대로 처리

따라서 1/n 과 1 사이에 있다.

$$
\begin{aligned}
1/(\log n) &= \Omega (1/n)
\\
&=O(1)
\end{aligned}
$$

99-2. $7n^5 -3n +2$

최고차항만 보자 $7n^5$

여기서 계수만 지우자 $n^5$

비교를 시작하자

$n^2$ 보다 크고 $2^n$ 보다 작다.

$$
\begin{aligned}
7n^5 -3n +2 &= \Omega(n^2)
\\
&= O(2^n)
\end{aligned}
$$

99-3. $(n^2+n)/(\log^2n+\log n)$

분자 중 큰 영향을 미치는 $n^2$만 뽑아내자

분모 중 큰 영향을 미치는 $\log^2n$만 뽑아내자

$n^2/\log^2n$

이는 $(n^2/\log^2 n)$ 와 Θ 관계이다.

$$
\begin{aligned}
(n^2+n)/(\log^2n+\log n) &= \Omega(n^2/\log^2 n)
\\
&= O(n^2/\log^2 n)
\end{aligned}
$$

99-4. $2^{\log^2n}$

지수 부분만 봤을 때 $\log^2n$ 는 n 보다 작다.

로그의 성질을 이용하여 변형을 하면

$$
\begin{aligned}
2^{\log^2n} &= 2^{\log n \log n}
\\
&= (2^{\log n})^{\log n}
\\
&= (n^{\log 2})^{\log^n}
\\
&= n^{\log^n}
\end{aligned}
$$

이므로 $n^2$ 보다 크다.

$$
\begin{aligned}
2^{\log^2n} &= \Omega(n^2)
\\
&= O(2^n)
\end{aligned}
$$

99-5. $3^n$

$$
\begin{aligned}
3^n &= \Omega(2^n)
\\
&= O(5^n)
\end{aligned}
$$