2023-09-25-1

master's theorem

Case 1. if $ \log_b{a} >k$

$\Theta(n^ {\log_b a })$

Case 2. if $\log_b{a}==k$

$$T(n) = \begin{cases} O(n^k\log^{p+1} n ) & \quad p>-1 O(n^k\log \log n ) & \quad p==-1 O(n^k)& \quad p \;less \;than \; -1. \end{cases}$$

Case 3. if $\log_b a $< $k$

$$T(n) = \begin{cases} O(n^k\log^p n ) & \quad p>=0 O(n^k) & \quad p\; less\;than\; 0. \end{cases}$$

hint : keep $f(n)$ as it is if $p>=0$

Special Recurrence $T(n) = T(\sqrt n )+f(n)$

minimal valid base case : n==2

$$T(n) = \begin{cases} 1 & \quad n==2 T(\sqrt n)+1 & \quad n>2. \end{cases}$$

No master's theorem. Should use substitution

$$T(n) = T(n^{1/2})+1 \quad\quad=T(n^{1/4})+1+1 \quad\quad=T(n^{1/8})+1+1+1 \quad \quad\quad=T(n^{1/2^k})+k$$

Here, let's assume $n=2^m$

then, $T(2^{m/2^k})+k=T(2^1)+\log_2{m}$ Here, since $m=\log_2{n}$,

$O(\log \log_2 n )$