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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://2ood.gitbook.io/2ood-knowledge-base/lecture-notes/algorithms/2023-09-18.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.