> 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-18.md).

# 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.

```c
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$

```c
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}$

```c
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$)