# Algorithm Quizzes

Yao Yao on August 3, 2020

## Quiz 1

Sort the following terms from slowest growing to fastest growing.

$(\log_2 n + 1)^3 \quad 7^{2n} \quad n^{\frac{1}{2}} \quad n^{\log_3 7} \quad 2^{7n} \quad 1000 (\log_2 n)^3 \quad 2^{\log_2 n} \quad n \log n \quad 5^{\log_3 n}$

• $2^{\log_2 n} = n$
• $5^{\log_3 n} = n^{\log_3 5}$

• $(\log_2 n + 1)^3 < 1000 (\log_2 n)^3$
• $n^{\frac{1}{2}} < 2^{\log_2 n} < n \log n$
• $5^{\log_3 n} < n^{\log_3 7} < 7^{2n} < 2^{7n}$

• $1000 (\log_2 n)^3 < n^{\frac{1}{2}}$
• $n \log n < 5^{\log_3 n}$

### 3. 综上

$(\log_2 n + 1)^3 < 1000 (\log_2 n)^3 < n^{\frac{1}{2}} < 2^{\log_2 n} < n \log n < 5^{\log_3 n} < n^{\log_3 7} < 7^{2n} < 2^{7n}$

## Quiz 2

(1) while (n > 2)
n = sqrt(n);
(2) while (n > 2)
n = log(n)


• $n(1) = n^{\frac{1}{2}}$
• $n(2) = n^{\frac{1}{4}}$
• ……
• $n(i) = n^{\frac{1}{2^i}}$

• $p = n^{\frac{1}{2^k}}$，两边同时 $2^k$ 次方，得：
• $p^{(2^k)} = n$，两边同时取对数，得：
• $(2^k) \times \log p = \log n$，两边再次取对数，得：
• $\log 2^k + \log \log p = \log \log n$，即：
• $k \times \log 2 + \log \log p = \log \log n$

$\because$ $\log \log p$ 和 $\log 2$ 都是常数，$\therefore k \in O(\log \log n)$ ，即算法复杂度为 $O(\log \log n)$

$\log^{\ast}n:={\begin{cases} 0 & {\mbox{if }} n \leq 1; \newline 1+\log^{\ast}(\log n) & {\mbox{if }} n>1 \end{cases}}$

• $n(1) = \log n$
• $n(2) = \log \log n$
• ……
• $n(i) = \log \log \cdots \log n$ ($i$ 个 $\log$)

\begin{aligned} \log^{\ast}(n) &= 1 + \log^{\ast}(\log n) \newline &= 2 + \log^{\ast}(\log \log n) \newline &= 3 + \log^{\ast}(\log \log \log n) \newline &= \dots \newline &= k + \log^{\ast}(\log \log \dots \log n) \newline &= k + \log^{\ast}(p) \end{aligned}

$\because$ $log^{\ast}(p)$ 为常数，$\therefore k \in O(\log^{\ast} n)$ ，即算法复杂度为 $O(\log^{\ast} n)$