## Lecture 03. Algorithmic Analysis
- Time Complexity
- Big-O notation
- Calculation rules
- Complexity Classes
Note:
Bo sung them:
- do phuc tap tuy thuoc vao du lieu dau vao
- amortized analysis
---
### Algorithm Complexity
- **Time Complexity**
- Space Complexity
---
### Algorithm Complexity
- **Time Complexity** of an algorithm estimates how much time the algorithm will use for some input. The idea is to represent the efficiency as a function whose parameter is the size of the input.
- By calculating the time complexity, we can find out whether the algorithm is fast enough **without implementing it**.
---
### Big-O notation
- $T(n)$ - time needed for an algorithm to run
- Algorithm has time complexity of $O(f(n))$ if there are some constants $c$ and $n_0$, such that $T(n) \le c\times f(n), \forall n \ge n_0$.
<img src="https://cdn.ucode.vn/uploads/1/upload/cYpiRgrT.png"/>
---
### Calculation rules
1. $O(c\times f(n)) =$ $O(f(n))$
2. Sequential: P1 with $O(f(n))$, then P2 with $O(g(n))$: $O(f(n) + g(n))$
3. $O(f(n) + g(n)) =$ $O(max(f(n), g(n)))$
4. Nested: P1 with $O(f(n))$, each iteration call P2 with $O(g(n))$: $O(f(n) \times g(n))$
5. Recursion: $O(f(n) \times c(n))$, where $f(n)$ - complexity of the function and $c(n)$ - number of function call
---
### Estimate Time Complexity
- Identify "**active operation**"
- Estimate number of its execution as a function of input data size
```python=
best = 0
for L in range(n):
for R in range(L, n):
best = max(best, sum(arr[L:R+1]))
print(best)
```
---
### Complexity classes
- $O(1)$ **constant-time** algorithm that does not depend on the input size. A typical constant-time algorithm is a direct formula that calculates the answer.
- $O(\log n)$ **logarithmic** algorithm often halves the input size at each step.
- $O(\sqrt{n})$ **square root** algorithm is slower than $O(logn)$ but faster than $O(n)$.
---
### Complexity classes
- $O(n)$ A **linear** algorithm goes through the input a constant number of times.
- $O(n\log n)$ often indicates that the algorithm **sorts** the input, or uses a data structure where each operation takes $O(\log n)$ time.
- $O(n^2)$ A **quadratic** algorithm often contains two nested loops.
---
### Complexity classes
- $O(n^3)$ A **cubic** algorithm often contains three nested loops.
- $O(2^n)$ often indicates that the algorithm iterates through **all subsets** of the input elements.
- $O(n!)$ often indicates that the algorithm iterates through **all permutations** of the input elements.
---
### Complexity classes
- An algorithm is **polynomial** (P Class) if its time complexity is at most $O(n^k)$ where k is a constant.
- In practice, $k$ is usually small, and therefore a polynomial time complexity roughly means that the algorithm is **efficient**.
- **NP-hard** problems are an important set of problems, for which no polynomial algorithm is known.
Note:
All the above time complexities except $O(2^n)$ and $O(n!)$ are polynomial. In practice, the constant $k$ is usually small, and therefore a polynomial time complexity roughly means that the algorithm is **efficient**.
---
### Function growth
<img src="https://cdn.ucode.vn/uploads/1/upload/MBdSmiRJ.png" class="element-left content-img" />
---
### Worst AC Algorithm
<img src="https://cdn.ucode.vn/uploads/1/upload/GgBrTYRc.png" class="element-center content-img" />
Assuming that a modern CPU can compute 100M operations in 1 second.
---
## Problem: maximum subarray sum
Given an array of n numbers, our task is to calculate the maximum subarray sum.
<img src="https://cdn.ucode.vn/uploads/1/upload/qMDvBtqF.png"/>
---
## Problem: maximum subarray sum
Given an array of n numbers, our task is to calculate the maximum subarray sum.
<img src="https://cdn.ucode.vn/uploads/1/upload/mUdsENtp.png"/>
---
## Problem: maximum subarray sum
<img src="https://cdn.ucode.vn/uploads/1/upload/mUdsENtp.png"/>
**Algorithm 1**: go through all possible subarrays,
calculate the sum of values in each subarray and maintain the maximum sum.
---
## Problem: maximum subarray sum
**Algorithm 1**:
```python=
best = 0
for L in range(n):
for R in range(L, n):
best = max(best, sum(arr[L:R+1]))
print(best)
```
Complexity?
---
## Problem: maximum subarray sum
**Algorithm 1**:
```python=
best = 0
for L in range(n):
for R in range(L, n):
best = max(best, sum(arr[L:R+1]))
print(best)
```
Complexity: **$O(n^3)$**
---
## Problem: maximum subarray sum
**Algorithm 2**:
```python=
best = 0
for L in range(n):
s = 0
for R in range(L, n):
s += arr[R]
best = max(best, s)
print(best)
```
Complexity?
---
## Problem: maximum subarray sum
**Algorithm 2**:
```python=
best = 0
for L in range(n):
s = 0
for R in range(L, n):
s += arr[R]
best = max(best, s)
print(best)
```
Complexity: **$O(n^2)$**
---
## Problem: maximum subarray sum
**Algorithm 3**: Dynamic Programming
- $f(k)$: the maximum-sum subarray that ends at position $k$. There are two possibilities:
- The subarray consists of a subarray that ends at position $k-1$, followed by the element at position $k$.
- The subarray only contains the element at position $k$.
- $f(k) =$ $max(f(k-1) + arr[k], arr[k])$
---
## Problem: maximum subarray sum
**Algorithm 3**:
```python=
best = s = 0
for k in range(n):
s = max(arr[k], arr[k] + s)
best = max(best, s)
print(best)
```
Complexity?
---
## Problem: maximum subarray sum
**Algorithm 3**: Kadane's algorithm
```python=
best = s = 0
for k in range(n):
s = max(arr[k], arr[k] + s)
best = max(best, s)
print(best)
```
Complexity: **$O(n)$**
---
## The End
---
{"metaMigratedAt":"2023-06-17T19:46:09.212Z","metaMigratedFrom":"YAML","title":"Thuc Nguyen's ADSA Course - Lecture 03. Algorithmic Analysis","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":6510,\"del\":489}]"}