Intro to Algo 2022 spring 紙筆作業 1
===
###### tags: `成大演算法春季課程`

請同學在 Word 檔或使用 MD 回答，
需手寫的部分可以選擇打字或是將手寫拍照貼上去，
最後請輸出成 PDF 繳交到 Moodle
請不要交 Word 檔，助教感謝各位同學的配合 :+1:
Deadline: **4/5 23:59**

## 第一題
Compare the following time complexity and arrange them in increasing order.

**( a )** $4^{\lg ⁡n}$
**( b )** $\log{⁡(n!)}$
**( c )** $2^n$
**( d )** $n!$
**( e )** $n^{\frac{1}{log⁡n}}$
**( f )** $(\log⁡{n})^{log⁡n}$

1. abefcd
2. ebafcd
3. ebacfd
4. abcdfe

## 第二題

Solve the following recurrences. Explain your answer:
**( a )** $T(n) = 2T(\sqrt{n}) + lg\space n$
**( b )** $T(n) = 2T(\frac{n}{2}) + n$
**\( c \)** Use the substitution method to solve $T(n) = 4T(\frac{n}{3}) + n$

## 第三題

Please prove that $lg(n!)=\theta(nlgn)$

## 第四題
Give asymptotic tight bound ( $\theta$ ) for question down below.
(Assume that $T(n)$ is a constant for sufficiently small $n$)
$$
T(n)=3T(\frac{n}{3})+ \frac{n}{\log^2 n}
$$

## 第五題
Use the **recursion-tree method** to give asymptotic tight bound( $\theta$ ) for question down below, and justify your answer. (Assume that $T(n)$ is a constant for sufficiently small n.) (Please draw the tree.)
$$
T(n)=T(\frac{n}{3})+T(\frac{n}{4})+n
$$