[알고리즘] 시간복잡도와 Master Theorem - 연습문제

이전 글 : [알고리즘] 시간복잡도와 Master Theorem

[알고리즘] 시간복잡도와 Master Theorem

---

시간복잡도와 Master Theorem - 연습문제

출처: “Algorithms,” Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGraw-Hill, 2008.

2.5. Solve the following recurrence relations and give a $\Theta$ bound for each of them.

(a) $T(n)=2 T(n / 3)+1$
(b) $T(n)=5 T(n / 4)+n$
(c) $T(n)=7 T(n / 7)+n$
(d) $T(n)=9 T(n / 3)+n^2$
(e) $T(n)=8 T(n / 2)+n^3$
(f) $T(n)=49 T(n / 25)+n^{3 / 2} \log n$
(g) $T(n)=T(n-1)+2$
(h) $T(n)=T(n-1)+n^c$, where $c \geq 1$ is a constant
(i) $T(n)=T(n-1)+c^n$, where $c>1$ is some constant
(j) $T(n)=2 T(n-1)+1$
(k) $T(n)=T(\sqrt{n})+1$

---

Solution

(a) By Master Theorem, $a=2, b=3, f(n)=1, h(n)=n^{\log _3 2}$

$f(n)<h(n), \quad T(n)=\Theta\left(n^{\log _3 2}\right)$

 

(b) By Master Theorem,

$a=5, b=4, f(n)=n, h(n)=n^{\log _4 5}$

$f(n)<h(n), \quad T(n)=\Theta\left(n^{\log _4 5}\right)$

 

(c) By Master Theorem, $a=7, b=7, f(n)=n, h(n)=1$

$f(n)>h(n), \quad T(n)=\Theta(n)$

 

(d) By Master Theorem, $a=9, b=3, f(n)=n^2, h(n)=n^2$

$f(n)=h(n), \quad T(n)=\Theta\left(n^2 \cdot \log n\right)$

 

(e) By Master Theorem, $a=8, b=2, f(n)=n^3, h(n)=n^3$

$f(n)=h(n), \quad T(n)=\Theta\left(n^3 \cdot \log h\right)$

 

(f) By Advanced Master Theorem, $a=49, b=25, k=\frac{3}{2}, p=1$

$a<b^k, p \geq 0, \quad T(n)=\Theta\left(n^{\frac{1}{2}} \log n\right)$

 

(g) $T(n)=T(n-1)+2=T(n-2)+2+2=\cdots=T(1)+2 n=\Theta(n)$

 

(h) $T(n)=T(n-1)+n^c=T(n-2)+(n-1)^c+n^c =\cdots=T(1)+1^c+2^c+\cdots+n^c \leq n \cdot n^c=\Theta\left(n^{c+1}\right)$

 

(i) $T(n)=T(n-1)+c^n=T(n-2)+c^{n-1}+c^n=T(u)+c^2+\cdots+c^n=\frac{c^{n-1}}{c-1}=\Theta\left(c^n\right)$

 

(j)
$T(n) = 2T(n-1)+1 = 2^2 T(n-2)+2 \cdot 1+1 = 2^3 T(n-3)+2^2 \cdot 1 + 2 \cdot 1 + 1 = 2^n \cdot T(0) + 2^{2-1}+2^{n-2}+\cdots+2^{1} + 1 = \Theta\left(2^n\right)$

 

(k) Suppose that $n=2^m, \quad T\left(2^m\right)=T\left(2^{\frac{m}{2}}\right)+1$

Let's $T\left(2^m\right)=S(m),\quad$ then $S(m)=S\left(\frac{m}{2}\right)+1=\Theta(\log m)$

So. $T(n)=\Theta(\log (\log n))$