---
# System prepended metadata

title: ADA HW1
tags: [ADA2020]

---

# 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)
    ![](https://i.imgur.com/6YylGY9.jpg)
    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)$。