Homework 14-2
=
###### tags: `Course - Algorithmics`
## 1
因為子程序可以在多項式時間完成，所以假設執行時間為$n^k$(k為常數)，執行c次需要$cn^k$的時間(c也是常數)，最後還要做一些也是多項是時間的工作，假設執行時間為$n^l$(l為常數)。
總耗時是$cn^k+n^l<n^m$(必定可以找到常數m)，所以還是多項式時間。
## 2
舉例，一個簡單的線性時間函式，被呼叫線性時間次：
(Dynamic Scoping is Enabled)

def my_function():
    for i from i to n:
        print(i)
    n = n * 2

input n
k = n
for i from 1 to k:
    my_function()

my_function()被執行了n次，且my_function()的執行時間是n，但是每當my_function()執行結束時，n就會加倍，所以總耗時非$n^2$而是$n\times2^n$，已經是指數時間了。