# Hw14 - Q2
###### tags: `演算法`, `109-2`

## Question
**Exercises 34.1-5**
Show that if an algorithm makes at most a constant number of calls to polynomial time subroutines and performs an additional amount of work that also takes polynomial time, then it runs in polynomial time.

Also show that a polynomial number of calls to polynomial-time subroutines may result in an exponential-time algorithm.

## Mein Answer

### 1
**題目**
呼叫 常數 次 polynomial-time 的子程式後，再多做一些 polynomial-time 的事情後，這支程式依舊會是 polynomial-time

**證明**
假設子程式總共有 $y$ 個，其中複雜度最高為 $O(n^k)$
多做的事情複雜度為 $O(n^d)$

則子程式們總複雜度最多為 $O(n^{yk})$
加上多做的事情，複雜度仍為 $O(n^{yk+d})$
因為 $y, k, d$ 為常數，所以這還是 polynomial

### 2
**題目**
呼叫 polynomial 次 polynomial-time 的子程式可能會讓整隻程式變成 exponential-time

**舉個正例：**
演算法魔王錦汶
在段考出 c 道演算法題目
結果錦汶出的每一題都超爆贛難
學生連看都看不懂，更遑論能答對了
不過因為怕被學校關切，錦汶設有補考機制，
補考的題目數依上一次題目數量而定，每一輪是上一輪的平方
假設學生在某次補考中，突然出竅竟然能及格，這次補考一共幾題？

轉換成蘇東code會變這樣

PROCEDURE JINWEN_HELL():
    c = sqrt(c)
    for round in 1 to n:
        c = ALGORITHM_QUIZ(c)
    
PROCEDURE ALGORITHM_QUIZ(q_count):
    q_count *= q_count
    for q in 1 to q_count:
        DO_ALGORITHM()
    return q_count
    
PROCEDURE DO_ALGORITHM()
    # Fuck up the question
    # Complexity: 1

| 第幾輪補考 | 有幾題 |
| ---------- | ------ |
| 1 | c |
| 2 | c^2 |
| 3 | c^3 |
| 4 | c^4 |
| n | c^n |

JINWEN_HELL 考試的輪數為 $n$，是 linear，小於 polynomial
ALGORITHM_QUIZ 的複雜度 $n^2$，也是 polynomial
但是總複雜度會變成 $c^n$，可怕的 exponential