# Week 3

:::info
:::spoiler Click to Open TOC
[TOC]
:::

## Question
:::info
:::spoiler Click to Open Question

### Check
- [x] Q1 yee
- [x] Q2 Mark
- [x] Q3 LXS
- [x] Q4 Chung
- [x] Q5 Xian
- [x] Q6 songchiu
- [x] Q7 Xian & Mark
:::

## Answer
### Q1
> - [name=yee]


#### 【Solution】
$\text{According to the definition}$
$\begin{aligned}
\\\lim_{n\to\infty}\dfrac{f(n)}{g(n)} &= c ≠ 0 \implies f(n) = \Theta(g(n))\\
\lim_{n\to\infty}\dfrac{f(n)}{g(n)} &= 0 \ f(n) = o(g(n)) \implies O(g(n))\\
\lim_{n\to\infty}\dfrac{f(n)}{g(n)} &= \infty \ f(n) = ω(g(n)) \implies Ω(g(n))
\end{aligned}$
#### 【a】
$\begin{aligned}
\lim_{n\to\infty} \dfrac{(lgn)^k }{n^ε}
&=\ \dfrac {d}{dn} \dfrac{(lgn)^k }{n^ε}\\
&=\ \lim_{n\to\infty} \dfrac{k(lgn)^{k-1}\dfrac {1}{n}}{εn^{ε-1}}\\
&=\ \lim_{n\to\infty} \dfrac{k(lgn)^{k-1}}{εn^{ε}}\\
&=\ \lim_{n\to\infty} \dfrac {d}{dn} \dfrac{k(lgn)^{k-1}}{εn^{ε}}\\
&= \lim_{n\to\infty} \dfrac {k(k-1)(lgn)^{k-2}}{ε^2n^{ε}}\ \cdots\\
&=\ \lim_{n\to\infty} \dfrac {k(k-1)(k-2)\cdots1}{ε^kn^{ε}}\\
\end{aligned}$
$\text{Let } n\ =\ \infty\ ,
\ \lim_{n\to\infty} \dfrac {k(k-1)(k-2)\cdots1}{ε^kn^{ε}}\ =\ \dfrac{1}{\infty}\ =\ 0_\#\\
\text{According to the definition when }\lim_{n\to\infty}\dfrac{f(n)}{g(n)}\ =\ 0\ ,\ f(n) \text{ equals } o(g(n)) \ \implies O(g(n)).$

| A | B | O | o | Ω | ω | Θ |
| --------- | ------- | ---- | ---- | --- | --- | --- |
| $lg(n)^k$ | $n^ε$ | yes | yes | no | no | no |

#### 【b】

$\begin{aligned}
\lim_{n\to\infty} \dfrac{n^k}{c^n}\ =\ \lim_{n\to\infty} \dfrac{klogn}{nlogc}
\end{aligned}$

$\text{Let } n\ =\ \infty\ ,\ \lim_{n\to\infty} \dfrac{klogn}{nlogc}\ =\ \dfrac{1}{\infty} =\ 0_\#\\
\text{According to the definition when }\lim_{n\to\infty}\dfrac{f(n)}{g(n)}\ =\ 0\ ,\ f(n) \text{ equals } o(g(n)) \ \implies O(g(n)).$

| A | B | O | o | Ω | ω | Θ |
| --------- | ------- | ---- | ---- | --- | --- | --- |
| $n^k$ | $c^n$ | yes | yes | no | no | no |

#### 【c】

$\begin{aligned}
\lim_{n\to\infty} \dfrac{\sqrt n}{n^{sin(n)}} &=\ \lim_{n\to\infty} n ^ {\dfrac{ 1 }{ 2 } - \sin (n)}\\
\end{aligned}$

$\because \lim_{n\to\infty} n ^ {\dfrac{ 1 }{ 2 } - \sin (n)}\text { is divergent.}\\
\therefore \text {There is no relation betwteen } \sqrt n \text { and }\ n^{sin(n)}.$

| A | B | O | o | Ω | ω | Θ |
| --------- | ------- | ---- | ---- | --- | --- | --- |
| $\sqrt{n}$ | $n^{\sin(n)}$ | no | no | no | no | no |

#### 【d】

$\begin{aligned}
\lim_{n\to\infty} \dfrac{2^n}{2^\frac{n}{2}}=\lim_{n\to\infty} 2^{n-\frac{n}{2}}=\ \lim_{n\to\infty}2^\frac{n}{2}\\
\end{aligned}$
$\text{ Let } n=\infty\ ,\ \lim_{n\to\infty}2^\frac{n}{2}\ = \infty\\ \text{According to the definition when }\lim_{n\to\infty}\dfrac{f(n)}{g(n)}= \infty \ ,\ f(n) \text{ equals } ω(g(n)) \implies Ω(g(n)).$

| A | B | O | o | Ω | ω | Θ |
| --------- | ------- | ---- | ---- | --- | --- | --- |
| $2^n$ | $2^{n/2}$| no | no | yes | yes | no |

#### 【e】

$\\\because c > 1\ \& \ {n\to\infty}\\
\therefore c^{ln(n)} = n^{ln(c)}$
$\begin{aligned}
\text{Thus , }\lim_{n\to\infty} \dfrac{n^{lg(c)}}{c^{ln(n)}} &= \lim_{n\to\infty} \dfrac{n^{lg(c)}}{n^{ln(c)}}\\
&= \lim_{n\to\infty} \dfrac{n^\dfrac{ln(c)}{ln(2)}}{n^{ln(c)}} \\
&= \lim_{n\to\infty} n^{\dfrac{ln(c)}{ln2}-\displaystyle ln(c)} \\
&= \lim_{n\to\infty} n^{\dfrac{ln(c)(1-ln2)}{ln2}}
\end{aligned}$
$\begin{aligned}
\\\because \dfrac{ln(c)(1-ln2)}{ln2} \text{ is a constant , Let } n = \infty \ ,\ \lim_{n\to\infty} n^{\dfrac{ln(c)(1-ln2)}{ln2}} = \infty
\end{aligned}$
$\begin{aligned}
\text{According to the definition when }\lim_{n\to\infty}\dfrac{f(n)}{g(n)}= \infty \ ,\ f(n) \text{ equals } ω(g(n)) \implies Ω(g(n)).
\end{aligned}$

| A | B | O | o | Ω | ω | Θ |
| --------- | ------- | ---- | ---- | --- | --- | --- |
| $n^{lg(c)}$ | $c^{ln(n)}$ | no | no | yes | yes | no |

#### 【f】

$\begin{aligned}
\lim_{n\to\infty}\dfrac{lg(n!)}{lg(n^n)} &\approx \lim_{n\to\infty}\dfrac{lg(\sqrt{2\pi n}\dfrac{n}{e}^n)}{nlgn} \\
&\approx \lim_{n\to\infty} \dfrac{nlgn - nlge + lg(\sqrt{2\pi n})}{nlgn}\\
&\approx\lim_{n\to\infty}\dfrac{nlgn}{nlgn} = 1_\#
\end{aligned}$

$\begin{aligned}
\text{According to the definition when }\lim_{n\to\infty}\dfrac{f(n)}{g(n)}= c ≠ 0 \ ,\ f(n) = \Theta(g(n)) \Longleftrightarrow f(n) = O(g(n))\ \ and \ \ f(n) = Ω(g(n)).
\end{aligned}$

| A | B | O | o | Ω | ω | Θ |
| --------- | ------- | ---- | ---- | --- | --- | --- |
| $lg(n!)$ | $lg(n^n)$ | yes | no | yes | no | yes |

### Q2
> - [name=Mark]


#### Hint
- non-negative $\rightarrow$ take absolute value
- cannot greater(less) than the other permanent
#### Ans
$f(n) = |sin(n)|$
$g(n) = |cos(n)|$

我發現我這題好水，只是我看不懂題目
我是:shit:
您是大佬，怎麼可能會是大便呢
0
乾你看 水到有剩
### Q3
> - [name=LXS]


#### 由大到小排序，框內的部分為 Equivalence class
#### 括弧內為大略所屬的複雜度範圍

$\begin{gather*}
2^{2^{n + 1}} \\
2^{2^n}\text{(雙重指數時間)} \\
(n+1)!=(n+1)n! \\
n!\text{(階乘時間)} \\
e^n \\
n\cdot 2^n \\
2^n \\
(3/2)^n\text{(指數時間)} \\
\boxed{\begin{gather*}
n^{\lg \lg n} = \lg{n}^{\lg n} \\
\end{gather*}} \\
(\lg n)! \\
n^3\text{(三次時間)} \\
\boxed{n^2 = 4^{\lg n}\text{(二次時間)}} \\
\boxed{lg(n!)\in\Theta(n\lg n)} \\
\boxed{2^{\lg n} = n\text{(線性時間)}} \\
(\sqrt 2)^{\lg n} = \sqrt n\text{(<1次時間)} \\
2^{\sqrt {2 \lg n}} \\
\lg^2 n \\
\ln n\text{(對數時間)} \\
\sqrt {\lg n}\\
\ln \ln n \\
2^{\lg^\ast n} \\
\boxed{\begin{gather*}
\lg^* n \in\Theta(\lg^\ast(\lg n))\\
\end{gather*}} \\
\lg(\lg^\ast n)\ \text{(迭代對數)} \\
\boxed{\begin{gather*}
n^{1/\lg n}=2 \\
1\text{(常數時間)}
\end{gather*}}
\end{gather*}$

#### 【證明】

$\begin{aligned}
n^{\lg \lg n} &= (2^{\lg n})^{\lg \lg n} = (2^{\lg \lg n})^{\lg n} = (\lg n)^{\lg n} \\
4^{\lg n} &= 2^{2\lg n} = 2^{\lg n^2} = n^2 \\
2^{\lg n} &= n \\
(\sqrt 2)^{\lg n} &= 2^{\frac 1 2 \cdot \lg n} = n^{\frac 1 2} = \sqrt n \\
\lg^*(\lg n) &= \lg^* n - 1 \\
n^{1/\lg n} &= n^{\lg 2/ \lg n} = n^{log_n 2} = 2 \\
lg((lg n)!) &= lgn\cdot lglgn \geq lgn^3=3lgn \\
2^{\sqrt {2 \lg n}}&=2^{\lg{n}\sqrt{\frac{2}{\lg{n}}}}=n^{\sqrt{\frac{2}{\lg{n}}}}<n^{\frac{1}{2}}
\end{aligned}$

$\text{By Stirling approximation} \\
\lg(x!) = (x+1/2)\lg x-x\lg e+O(1)...= \Theta(xlgx) \\
let\ x = \lg n \\
(\lg n)! = x! = 2^{\lg x!} \\
2^{(x+1/2)\lg x-x\lg{e}}=2^{\lg x^{(x+1/2)}}\cdot 2^{-x\lg e}=x^{x+1/2}\cdot 2^{-x\lg e} \\
=\frac{1}{n^{\lg e}}\lg n^{\lg{n}+1/2}=\frac{\sqrt{\lg{n}}}{n^{\lg e}}\lg{n}^{\lg{n}}\le \lg{n}^{\lg{n}}$

**迭代對數**

#### b.
【解題思路】

When even $2^{2^{n+2}}$ grows faster than $g_i(n)$ and when odd $\frac{1}{n}$ is grows slower than $g_i(n)$. Therefore $f(n)$ is neither $O(g_i(n))$ nor $\Omega(g_i(n))$.
\begin{align*}
f(n)=
\begin{cases}
2^{2^{n+2}} & \text{if $n$ is even},\\
\frac{1}{n} & \text{if $n$ is odd}.
\end{cases}
\end{align*}

### Q4
> - [name=Chung]


#### a.

$\text{ Disprove.}$
$\text{ Let } f(n) = n ,\ g(n) = n^{2}.n=O(n^{2}) \ but \ n^{2} ≠ O(n).$
#### b.
$\text{ Disprove.}$
$\text{ Let } f(n) = n ,\ g(n) = n^{2}.n+n^{2} ≠ \Theta(min(n^{2}, n))\ = \Theta(n).$
#### c.
$\text{ Prove.}$
$\ f(n) = O(g(n)) \ means \ 0 \le \ f(n) \le \ c\cdot\ g(n) \ for \ all \ n≥n_0 \,\ for \ some \ constants\ c, \ n_0\ >\ 0\\
\text{Thus,} \ 0 \le \ lg({f(n)}) \le \ lgc + lg({g(n)}) \le \ k \cdot\ lg({g(n)})
\\ 0 \le \ lg({f(n)}) \le \ k \cdot\ lg({g(n)})\\
\text{Therefore,} \ lg({f(n)}) = O(lg({g(n)}))
.$

#### d.
$\text{ Disprove.}$
$\text{ Let } f(n) = 2n ,\ g(n) = n.\ 2n = O(n) \
\text{Thus,}\ 2^{2n} = 4^n ≠ O(2^n).$

#### e.
$\text{ Disprove.}$
$\ ∃c,n_0:∀n≥n_0, \ 0 \le \ f(n) \le \ c\cdot\ f(n)\cdot\ f(n)\ \
\text{However,} \ if \ f(n)<1,\ for \ all \ n\\ This \ conjecture \ does \ not \ hold .$

#### f.
$\text{ Prove.}$
$\ 0 \le \ f(n) \le \ c\cdot\ g(n)\ for \ all \ n≥n
_0\ such \ that \ the \ constants \ c, \ n_0 > 0 \\
g(n) = Ω(f(n))\ means \ 0\le \ \frac{1}{c} \cdot\ f(n)\le \ g(n)\\
\text{Thus,}\ 成立.$

#### g.
$\text{ Disprove.}$
$\text{ Let } f(n) = 4^n ,\ f( \frac{n}{2} ) = 4^\frac{n}{2} \\
\text{Thus,}\ 4^n ≠ \Theta(4^\frac{n}{2}) = \Theta(2^n).$

#### h.
$\text{ Prove.}$
$\text{ Let } g(n) = o(f(n)) ,\ f(n) + g(n) = \Theta(f(n))\\
0 \le \ g(n) \le \ c\cdot\ f(n)\ for \ all \ n≥n_
0\ such \ that \ the \ constants \ c, \ n_0 > 0 \\
f(n) \le \ f(n)+g(n) \le \ c\cdot\ f(n) + f(n) = (c+1)\cdot f(n)\\
\text{Thus, }\ f(n)+ o(f(n)) = \Theta(f(n)).$
#### i.
$\text{ Disprove.}$

$\text{ Let } f(n) = sin(n)+2 = \Theta(1) ,\ g(n) = 1 \\
\frac{f(n)}{g(n)} = sin(n)+2 \\ lim\frac{f(n)}{g(n)} \ is \ divergence \ limit.$

> 題目有誤
> 

### Q5
> - [name=Xian]


$\begin{aligned}
T(n)&=2T(\sqrt{n})+1 \qquad let\ m = \lg{n},\ n = 2^m\\
T(2^m)&=2T(2^\frac m2)+1 \qquad let\ S(m) = T(2^m)\\
S(m)&=2S(\frac m2)+1\\
\end{aligned}$
#### 【解1】
$\text {By Master Theorem, k=0 a= 2 b= 2}\implies k < log_{2}{2} = 1$

$\begin{aligned}
\therefore S(m)&=\Theta(m^{log_{2}{2}})=\Theta(m)\\
T(2^m)&=\Theta(m)\\
T(n)&=\Theta(\lg{n})_\#
\end{aligned}$

#### 【解2】 (我不確定是不是對的)
$\text{Suppose }\color{red}{S(m)\leq cm+d,}\\
\begin{aligned}
S(m)&\leq 2(c\frac m2 + d)+1\\
&\leq cm+2d+1 \qquad(d\leq-1)\\
&\leq cm+d
\end{aligned}$

$\text{Then, suppose }\color{red}{S(m)\geq cm+d,}\\
\begin{aligned}
S(m)&\geq 2(c\frac m2 + d)+1\\
&\geq cm+2d+1 \qquad(d\geq-1)\\
&\geq cm+d\\
\text{Thus, }&S(m) = \Theta(m)\\
&T(n)=\Theta(\lg{n})_\#
\end{aligned}$

### Q6
> - [name=songchiu]


#### Master Theorem

#### a.
$a = 2,\; b = 2,\; f(n)=n^3$
$\text{By Master Theorem, } \Theta(n^3)$

#### b.
$a = 1,\; b = \dfrac{10}{9},\; f(n)=n$
$\text{By Master Theorem, } \Theta(n)$

#### c.
$a = 16,\; b = 4,\; f(n)=n^2$
$\text{By Master Theorem, } \Theta(n^2 \; log\; n)$

#### d.
$a = 7,\; b = 3,\; f(n)=n^2$
$\text{By Master Theorem, } \Theta(n^2)$

#### e.
$a = 7,\; b = 2,\; f(n)=n^2$
$\text{By Master Theorem, } \Theta(n^{log_2 \; 7})$

#### f.
$a = 2,\; b = 4,\; f(n)=\sqrt{n}$
$\text{By Master Theorem, } \Theta(\sqrt{n} \times log\; n)$

#### g.
$n + (n-1) + (n-2) + ... + 1 = \Theta(n^2)$

#### h.
$T(n) = T(n^{\frac{1}{2}}) + 1 = T(n^{\frac{1}{4}}) + 2 = T(n^{\frac{1}{8}}) + 3 = ... = T(n^{\frac{1}{2^k}}) + k$
$\text{Let } n = 2^{2^k},\;log \; n = 2^k , \; k=log \; log \; n , \; T(n) = \Theta(log \; log \; n)$

ref: [Master Theorem](https://www.programiz.com/dsa/master-theorem)

### Q7
> - [name=Xian & Mark(我只負責打字Q)]


#### a.
$T(n) = 4T(\frac{n}{3}) + n lg n$
$\text{By Master Theorem, }$
$a = 4, b = 3, f(n) = n lg n$
$1 < log_{3}{4} < 2$
$\because f(n) = O(n^{log_{3}{4-ε}})$
$\therefore T(n) = \Theta(n^{log_{3}{4}})_\#$

#### b.
$\begin{aligned}
T(n)&=3T(\frac{n}{3})+\frac{n}{lg{n}} \\
&=3(3T(\frac{n}{9})+\frac{\frac{n}{3}}{lg\frac{n}{3}})+\frac{n}{lg{n}} \\
&=9T(\frac{n}{9})+\frac{n}{lg{n}-log{3}}+\frac{n}{lg{n}} \\
&=9(3T(\frac{n}{27})+\frac{\frac{n}{9}}{lg\frac{n}{9}})+\frac{n}{lg{n}-log{3}}+\frac{n}{lg{n}} \\
&=27T(\frac{n}{27})+\frac{n}{lg{n}-2lg{3}}+\frac{n}{lg{n}-lg{3}}+\frac{n}{lg{n}} \\
&=... \\
&=nT(\frac{n}{n})+\sum\limits_{i=0}^{log_{3}{n}-1}\frac{n}{lg{n}-ilg{3}} \\
&=nT(1)+\sum\limits_{i=1}^{log_{3}{n}}\frac{n}{lg{n}-(i-1)lg{3}} \quad (n=3^k, k=log_{3}{n}) \\
&=nT(1)+\sum\limits_{i=1}^{k}\frac{n}{k-(i-1)lg{3}} \qquad \; (\because \sum\limits_{i=0}^{k-1}\frac{1}{k-i} \approx log{k} \; \therefore k=log_{3}{n}) \\
&=\Theta(nlog{log_{3}{n}})\\
&=\Theta(nlg{lgn})_\#
\end{aligned}$

#### c.
$\begin{aligned}
T(n)&=4T(\frac{n}{2})+n^2\sqrt{n} \\
&=4T(\frac{n}{2})+n^\frac{5}{2} \\
\end{aligned}$
$\text{By Master Theorem, } a=4 \;\; b=2 \;\; c=\frac{5}{2}$
$log_{b}{a}=log_{2}{4}=2$
$f(n)=n^{2+\frac{1}{2}}=O(n^{log_{2}{4}+ε})$
$T(n)=\Theta(f(n))=\Theta(n^{2.5})$
$4f(\frac{n}{b}) \leq cf(n)$
$\begin{aligned}
4f(\frac{n}{2})&=4(\frac{n}{2})^{\frac{5}{2}} \\
&=4n^{\frac{5}{2}}\cdot2^{-\frac{5}{2}} \\
&=2^2 \cdot 2^{-\frac{5}{2}} \cdot n^{\frac{5}{2}} \\
&=2^{-\frac{1}{2}} \cdot n^{\frac{5}{2}} \\
&\leq cf(n)
\end{aligned}$
$\because c \geq \frac{1}{\sqrt 2}\text{即成立}$
$\therefore c<1 \text{成立}$
#### d.
$\begin{aligned}
T(n)&=3T(\frac{n}{3}-2)+\frac{n}{2} \\
&\approx =3T(\frac{n}{3})+\frac{n}{2}
\end{aligned}$
$\text{By Master Therom, } \; a=3 \; b=3 \; c=1$
$log_{3}{3}=1 \; f(n)=n^1=\Theta (n^{log_{3}{3}})$
$T(n)=\Theta (nlgn)_\#$
#### e.
$\begin{aligned}
T(n)&=2T(\frac{n}{2})+\frac{n}{lg{n}} \\
&=2(2T(\frac{n}{4})+\frac{\frac{n}{2}}{lg\frac{n}{2}})+\frac{n}{lg{n}} \\
&=4T(\frac{n}{4})+\frac{n}{lg{n}-log{2}}+\frac{n}{lg{n}} \\
&=... \\
&=nT(\frac{n}{n})+\sum\limits_{k=0}^{log_{3}{n}-1}\frac{n}{lg{n}-k} \\
&=nT(1)+\sum\limits_{k=1}^{lg{n}}\frac{n}{lg{n}} \\
&=\Theta(nlg{lg{n}})_\#
\end{aligned}$
#### f.
$T(n)=T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+n$
$\text{Suppose} \; T(n) \leq Cn,$
$\begin{aligned}
T(n) &\leq C\frac{n}{2}+C\frac{n}{4}+C\frac{n}{8}+n=\frac{7}{8}Cn+n \\
&\leq Cn(n \geq 8) = O(n)
\end{aligned}$
$\text{Suppose} \; T(n) \geq Cn,$
$\begin{aligned}
T(n) &\geq C\frac{n}{2}+C\frac{n}{4}+C\frac{n}{8}+n=\frac{7}{8}Cn+n \\
&\geq Cn(n \leq 8) = \Omega(n)
\end{aligned}$
$T(n)=\Theta(n)$
#### g.
$\begin{aligned}
T(n)&=T(n-1)+\frac{1}{n} \\
&=T(n-2)+\frac{1}{n-1}+\frac{1}{n} \\
&=... \\
&=\sum\limits_{i=0}^{n-1}{\frac{1}{n-i}}\\
&=\sum\limits_{i=1}^{n}{\frac{1}{i}}\\
&= \Theta(lgn)
\end{aligned}$

#### h.
$\begin{aligned}
T(n)&=T(n-1)+lgn \\
&=T(n-2)+lg{(n-1)}+lgn \\
&=... \\
&=\sum\limits_{i=0}^{n-1}{lg{(n-i)}} =\sum\limits_{i=1}^{n}{lg{(n)}} \\
&=lg(n!) \leq lg{n^n}=nlgn=\Theta(nlgn) \\
\end{aligned}$
$\text{Or By Stirling's Formula,} \;\; lg(n!)=\Theta(nlgn)$
#### i.
$\begin{aligned}
T(n)&=T(n-2)+\frac {1}{lgn} \\
&=T(n-4)+\frac {1}{lg{(n-2)}}+\frac {1}{lgn} \\
&=... \\
&\implies T(2)+\sum\limits_{k=2}^{\frac{n}{2}}{\frac{1}{lg{2k}}} \;\; n \;\;is \;\; even \\
&\implies T(1)+\sum\limits_{k=2}^{\frac{n-1}{2}}{\frac{1}{lg{2k}}} \;\; n \;\; is \;\; odd\\
\end{aligned}$
<!-- :::spoiler 請點開附圖(我有看懂，但我不知道不要把這個寫到過程 by Mark)
::: -->
$\begin{aligned}
T(n)&=
\left\{
\begin{array}{c}
T(2)+\sum\limits_{k=2}^{\frac{n}{2}}{\frac{1}{lg{2k}}} \;\; n \;\;is \;\; even \\
T(1)+\sum\limits_{k=2}^{\frac{n-1}{2}}{\frac{1}{lg{2k}}} \;\; n \;\; is \;\; odd\\
\end{array}
\right. \\
&=\Theta(1)+O(\frac {n}{lgn}) \quad li(x)=\int_0^x \frac{dy}{ln(y)} \implies li(x)=O(\frac{x}{ln(x)})\\
&=O(\frac {n}{lgn})
\end{aligned}$
#### j.
$T(n)=\sqrt n T(\sqrt n)+n \quad let \;\; n=2^m \;\; m=lgn$
$T(2^m)=2^{\frac{m}{2}}T(2^{\frac{m}{2}})+2^m$
$\frac {T(2^m)}{2^m}= \frac {T(2^{\frac{m}{2}})}{2^{\frac {m}{2}}}+1\quad let\ Q(m)=\frac{T(2^m)}{2^m}$
$\text {By Master Therom,} \; Q(m)=Q(\frac {m}{2})+1 \;\; a=1 \;\; b=2 \;\; c=0 \;\;n^0 = n^{log_{2}{1}}$
$\because f(m)=\Theta(m^{log_{2}{1}}) \implies \therefore Q(m)=\Theta(lgm)=\frac{T(2^m)}{2^m}$
$T(2^m)=2^mQ(m)=2^m\Theta(lgm)=\Theta(2^mlgm)$
$m=lgn \text{代回} \implies T(n)=\Theta(nlglgn)_\#$

#### k.
$\begin{aligned}
T(n)&=\sqrt nT(n-1)+n \\
&=\sqrt n(\sqrt {n-1}T(n-2)+n-1)+n \\
&=\sqrt n\sqrt {n-1}T(n-2)+\sqrt nn-\sqrt n+n \\
&=... \\
&=\sqrt n \sqrt{n-1}...\sqrt 2 \sqrt 1 \cdot T(n-n)+n^{\frac {5}{2}}+n-n^{\frac {5}{2}}+n^{\frac {3}{2}} \\
&=\sqrt {n!}+\Theta(n^{\frac {5}{2}}) \implies \text {By Stirling's Formula, } =O(n^{\frac {n}{2}})\\
\end{aligned}$