# ADA HW1
### B08902045 資工二 袁紹奇
###### tags: `ADA2020`

---

### Problem 5 - Time Complexity & Recurrence

1. #### Asymptotic Notations
(a)
$$
\forall c, n_0\ \exists n=\lceil {\max (c^2, n_0)\over 2\pi} +1 \rceil \cdot 2\pi \ge n_0 \ \text{s.t}\\
{\sqrt n} > cn^{\sin n} = cn^0 = c
$$
Therefore $\sqrt n \ne O(n^{\sin n})$.

(b)Since $f(n)=\Theta(g(n))$, we get
$$
c_1g(n)\le f(n)\le c_2g(n)\\
\log c1+\log(g(n))\le \log(f(n))\le \log c_2+\log(g(n))
$$
Note that for sufficiently large $n_0$, for all $n>n_0$, the following 2 inequalities would be satisfied.
$$
\log(g(n))\ge 2\cdot |\log c_1|\\
\log(g(n))\ge 2\cdot |\log c_2|
$$
then,
$$
{1\over 2}\log(g(n))\le\log c_1+\log(g(n))\\
\log c_2+\log(g(n))\le2\log(g(n))
$$
choose $c_3={1\over 2}, c_4=2$, we have
$$
c_1\log(g(n))\le\log(f(n))\le c_2\log(g(n))
$$
Therefore, $\log(f(n))=\Theta(g(n))$.

(*discussed with b08902119 王風意*)

(c\) let
$$
f_1=2^n=O(g_1(n))=O(2^n)\\
f_2=2n=O(g_2(n))=O(n)\\
$$
we have
$$
f_1\circ f_2(n)=2^{2n}=4^n\ne O(g_1\circ g_2(n))=O(2^n)
$$
Therefore we found a counterexample.

(d)
Note that when $n \ge 2|a|$, we have
$$
0 \le {1\over 2}n \le n+a \le 2n
$$
choose $n_0\ge 2|a|, c_0=2^b, c_1=({1\over 2})^b$,when $n\ge n_0$ we have
$$
c_1n^b=({n\over 2})^b\le (n+a)^b \le (2n)^b = c_0n^b
$$
Therefore $(n+a)^b=\Theta (n^b)$
[*reference*]: https://math.stackexchange.com/questions/267341/show-that-n-ab-thetanb

2. #### Solve Recurrences
(a) Let $n=127k$, where $k\in \mathbb Z$, we have
$$
T(n)=127({1\over \log n}+{1\over \log{n-127}}+...+1)
$$
Since $\log x \le 127(\log x-1)$ $\forall x\ge k$, where $k$ is a constant, we have
$$
T(n)\le\sum_{x=k}^{n}{1\over \log x}\le 127\sum_{x=k}^{n}{{\log x-1}\over \log^2 x}\le\int_{k}^{n} {{\log x-1}\over \log^2 x}dx=127({n\over \log n}-\text constant)
$$
Thus, $T(n)=O(n\log n)$.
Also, note that ${1\over \log n}\le{1\over \log(n-127)}\le ...$, we have
$$
T(n)\ge 127({1\over \log n}\cdot {n\over 127})={n\over \log n}
$$
Thus, $T(n)=\Omega({n\over \log n})$.
In conclusion, $T(n)=\Theta({n\over \log n})$.

(*discussed with b08902119 王風意*)

(b)
By the graph of the recursion tree, we observe that
$$
T(n)\le 8n\log n
$$
so $T(n)=O(nlogn)$.
Also,
$$
T(n)=T(n/2)+T(n/4)+T(n/8)+nlogn\ge nlogn
$$
we can infer that $T(n)=\Omega(nlogn)$.
Thus, $T(n)=\Theta(n\log n)$.

(c\) Use Master Theorem. Since $n\log n=O(n^{\log_2 4-\epsilon})=O(n^{2-\epsilon})$ for some $\epsilon>0$, the recurrence is Case 1. Therefore, $T(n)=\Theta (n^2)$.

(d) let $n=2^k$, we can rewrite the recurrence to
$$
T(2^k)=2^{k\over 2}T(2^{k\over 2})+2^k\\
=2^{k\over 2}(2^{k\over 4}T(2^{k\over 8})+2^{k\over 2})+2^k\\
=2^{k\over 2}(2^{k\over 4}(...)+2^{k\over 2})+2^k
$$
Keep expending, we get
$$
T(2^k)=2^{k\sum_{i=1}^{\log_2k}2^{-i}}T(1)+\log_2k\cdot 2^k\le 2^k+2^k\log_2k
$$
Therefore, substitute $2^k$ with $n$, we have
$$
T(n)\le n+n\log\log n=O(n\log\log n)
$$
Furthermore, use induction to prove $T(n)=\Omega(n\log\log n)$.
$T(1)$ is trivial. Let
$$
k\log\log k\le T(k)=\sqrt kT(\sqrt k)+k
$$
We have
$$
k^2\log\log k^2=k^2\log(2\log k)=k^2(\log2 + \log\log k)\\
\le T(k^2)=kT(k)+k^2=k(\sqrt kT(\sqrt k)+k)+k^2=k\sqrt kT(\sqrt k)+2k^2
$$
Therefore, with $T(n)=\Omega(n\log\log n)$ and $T(n)=O(n\log\log n)$, we know that $T(n)=\Theta(n\log\log n)$.
[*reference*]: https://mropengate.blogspot.com/2015/04/algorithm-ch1-master-theorem-super.html

### Problem 6 - Viennese Waltz
以下題目(1~3)請參考第4題的前綴和陣列和找長方形權重的方法。
~~可以先看第四題，如果錯了再看前三題就好0.0。~~

1. 一開始前綴和陣列需要花到$O(n^2)$的時間複雜度，接下來，對於每個查詢，需要$O(1)$的時間，我們有$k$個查詢，因此總複雜度是$O(n^2+k)$。

2. 枚舉每個長方形，需要決定頂、底、左寬和右寬，也就是$O(n^4)$，對於每個枚舉的長方形，如果周長大於L就不要算邊上權重和，然後每次更新最大的滿足周長小於等於L的最大的邊上權重和，時間複雜度是$O(n^4+n^2)=O(n^4)$。

3. 參考第四題的方法，只是不用使用sliding window和建表，只要在case 1 和 case 2 中分別查詢最大的"$\sqsupset$"和最大的"$\sqsubset$"即可，最後再合併為長方形，查詢最大需要$O(n)$，枚舉全部並查詢需要$O(n^2)\cdot O(n)=O(n^3)$。總共複雜度為$O(n^3+n^2)=O(n^3)$。

4. 我們使用D&C，對於每個$N\times N$的長方形，平分切成四塊${N\over 2}\times {N\over2}$的小長方形下去遞迴。

首先，建立一個size為$N\times N$的前綴和陣列，也就是說，對於一個$(i, j)$的詢問可以在$O(1)$時間內找到範圍為$[0,i][0,j]$的所有權重的和，那麼對於左上角為$(i_1, j_1)$，右下角為$(i_2, j_2)$的任意長方形來說，可以由四個簡單加減法得出答案，因此找到任意長方形"內"權重和是$O(1)$，找到任意長方形"邊上"權重總和也是$O(1)$。

再來，對於每一個遞迴的函式來說，設$a,b,c,d$為滿足周長小於$L$的四個小長方形的最大邊上權重和，接下來要討論橫跨多於一個小長方形的情況，也就是combine所處理的事情，情況有兩種，分別為：
1. 最大邊上權重和的長方形橫跨兩個小長方形，此情況有四種。
2. 最大邊上權重和的長方形橫跨四個小長方形，此情況只有一種。

case 1可以枚舉所有情況，以左上和右上兩個小長方形為例，找到一個上邊$k_1$(需要$O({n\over 2})$)，找一個下邊$k_2$(需要$O({n\over 2})$)，接下來往左右分別建表，以右邊為例，儲存$n\over 2$個在該位置左邊的最大的コ的值和位置；左邊也做同樣的事，建表需要$O(2({n\over 2}))$。

接下來運用sliding window，找到每個上邊是$k_1$，下邊是$k_2$且周長是$L$以內的邊上權重和最大的長方形，再找到其中最大的值，此操作需要$O({n\over 2})$

因此，case 1總共需要$O({n\over 2})\cdot O({n\over 2})\cdot (O(2({n\over 2}))+O({n\over 2}))=O(n^3)$，總共需要做四次，分別是左上左下、左上右上、右上右下、左下右下，複雜度也會是$O(n^3)$。

接下來是case 2，跟上面類似，差別只是在這次把左邊的小長方形看成是case 1的兩個小長方形拼起來，右邊亦同。再者，case 2找上邊和下邊也都需要$O({n\over 2})$，對於每個上邊和下邊建表、sliding window也需要$O({n\over 2})$，總複雜度跟case 1一樣是$O(n^3)$。

最後，我們需要回傳這case 1、case 2和$a,b,c,d$的最大值，此操作需要$O(1)$。
綜上所述，我們可以寫出遞迴關係式
$$
T(n)=
\begin{cases}
O(1) & \text{if } x\le 1\\
4T({n\over 2})+n^3 & \text{otherwise}
\end{cases}
$$
使用Master Theorem，因為
$$
n^3=\Omega(n^{\log_2 4})=\Omega(n^2)\\
4(({n\over2})^3)\le c\cdot n^3
$$
for some constant $c<1$ and all sufficiently large $n$
我們可以知道他是Master Theorem的case 3，因此此演算法的複雜度為$O(n^3)$。