> For the complete documentation index, see [llms.txt](https://2ood.gitbook.io/2ood-knowledge-base/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://2ood.gitbook.io/2ood-knowledge-base/lecture-notes/algorithms/2023-09-25-1.md).

# 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 )$