2023-09-18

Introduction

Summary

keywords

TODO

HW

Exercise*

Next time Recurrence $T(n) = 2T(n-1)+1$

---

Recap

practice thinking in a recursive manner

First approach base condition

• think about smallest valid input

• think about the smallest piece of recursion

=> hypothesis

• think about how to make the phase smaller/bigger

=> induction

• think about how topull the next recursion and use it.

---

Chapter 4 in book

Recurrence Relation

Find the time complexity of some recursion codes.

method of finding time complexity

• Recursion Tree method

• Substitution method

• masters theorem

memo. Recursion is naturally function of a decreasing form. How? subtraction & division.

1. Decreasing Recurrence $T(n)=T(n-1)+1$

We denote the function as T.

Void Test(int n) {
	if(n>0){
		printf("%d",n)
		Test(n-1);
	}  
}

This has time complexity $\Theta(n)$. Two primitive steps : comparison, printing. for each recurrence, this takes $2+T(n-1)$ steps. Two is a constant, so it is basically same as 1. n+1 function calls, n prints.

#todo : try to draw of recursive tree.

memo. linear(and quadratic) function, you can represent with theta. n! function, you cannot represent with theta.

Let's use substitution method this time. Base Condition:

Do not forget to write base condition!

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

Substitution: $T(n) = T(n-1)+1$ $\quad\quad=T(n-2)+2$ $\quad\quad=T(n-3)+3$ $\quad...$ $\quad\quad=T(n-n)+n$ $\quad\quad=1+n$

IN TEST, should substitute at least 3 times. IN TEST, If possible, write in Theta function.

2. Decreasing Recurrence $T(n) = T(n-1)+n$

Void Test(int n){
	if(n>0){
		for(int i=0;i<n;i++) {
			printf("%d",n);
		}
		Test(n-1);
	}
}

Let's use substitution. Base Condition:

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

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

3. Decreasing Recurrence $T(n)=T(n-1)+\log{n}$

Void Test(int n){
	if(n>0) {
		for(int i=0;i<n;i*=2){
			printf("%d",n);
		}
	}
	Test(n-1);
}

For each for loop, it takes $\log{n}$ times of calculation. $# ;of ;calculations = \log{1}+\log{2}+\log{3}+...+\log{n} = \log n! $ So, in upper bond, $\log n!$<$=\log n^n$ $O(\log{n^n}) = O(n\log{n})$

#todo : derive it with substitution method.

Shortcuts #1

$T(n)=T(n-1)+1 => \Theta(n)$ $T(n)=T(n-1)+n => \Theta(n^2)$ $T(n)=T(n-1)+\log{n} => O(n \log{n})$

The next order of remainder factors. What if $T(n) = T(n-C) +1$? The $C$ doesn't matter. (unless $c->\infty$)