2023-09-20

Introduction

Summary

keywords

TODO

HW $T(n) = T(n/2) +n$ use Substitution $T(n) = 8T(n/2) + nlogn$ Assignment document.

Exercise*

Next time

---

Recap

Recursion Tree Method, Substitution,

1. scrutinize the code

2. write the recursion formula

3. do the substitution.

How do you reduce the size of the input? ex. substraction, division, taking a root.

shortcut method for recurrence relation.

---

3. Decreasing Recurrance $T(n)=2*T(n-1)+1$

example. fibonacci, subset finding problem.

Void Test(int n) {
	if(n>0) {
		stmt;
		Test(n-1);
		Test(n-1);
	}
}

$$
\begin{equation*}
T(n) = \begin{cases}
1 & \quad n=0 \\
2*T(n-1)+1 & \quad n>0.
\end{cases}
\end{equation*}
$$

Substitution: $T(n) = 2T(n-1)+1$ $\quad\quad=T(n-2)+1$ $\quad\quad=2T(n-2)+21+1$ $\quad\quad=2T(n-3)+221+21+1$ $\quad...$ $\quad\quad=2T(n-k)+2^{k-1}+2^{k-2}+2^{k-3}+...+2^2+2+1$

Time complexity of $O(2^n)$.

Masters Theorem

$for \; T(n) = aT(n-b)+f(n)$ where $a>0,;b>0,; f(n)= O(n^k); \text{where}; k>=0$

Case 1. $a==1;$

$O(f(n)*n)$ #todo : fill out examples.

Case 2. $a>1$

$O(n^ka^{n/b})$ #todo : fill out examples.

Dividing Function

For dividing functions, it is important n should never be zero in base case.

base case should not be of input size 0 Because we cannot divide by 0..

1. Dividing Recurrence $T(n)=T(n/2)+1$

Void Test(int n) {
	if (n>1) {
		stmt;
		Test($$
\begin{equation*}
T(n) = \begin{cases}
1 & \quad n=0 \\
2*T(n-1)+1 & \quad n>0.
\end{cases}
\end{equation*}
$$n/2);
	}
}

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

smallest valid input should be $n=1$.

How many 1's are added? $n=2^k$ $k=\log n$ So, Time complexity is $\Theta(\log n)$

Let's use substitution method this time. $T(n) =T(n/2)+1$ $\quad\quad=T(n/2^2)+1+1$ $\quad\quad=T(n/2^3)+1+1+1$ $\quad...$ $\quad\quad=T(n/2^k)+k$ $\quad\quad=1+\log n$

2. Dividing Recurrence $T(n) = 2T(n/2)+n$

#todo : check the picture taken and see the recursive tree method.

1. draw each steps

2. find each step's time complexity (A)

3. find the base condition, and find the layer depth. (B)

4. time complexity = $A * B$

#todo : write about substitution

time complexity is $\Theta(n\log n)$