[\<- 04/08](04-08.md)

---

## Review - Data Structure

What is a data structure?
- How data is organized in memory (or hard disk)

Why do we care about data structure?
- Efficiency - time/space efficiency
- How to measure time efficiency?
	- Count # of operations
	- What types of operations do we care about?
		- Insertion
		- Deletion
		- Access/Search
		- Min/Max
		- Union/Merge
	- When do we care?
		- We only care about the one with the highest impact on efficiency

## Review - Big-O Notation

The correct form of big-O
- Drop all but the fastest-growing term
- Drop the constant coefficient of the remaining term
- e.g `1500n^2 + 4n + 3log(n) + 2` -> `1500n^2` -> `n^2`
	- Big-O notation for this example would be O(n^2)

How to evaluate the big-O for a piece of code?
- We mainly care about repetitive operations
	- Operations that are only executed once (or constant times) will be ignored
- Loops
	- Single layer loop
	- Nested loop

## Summary: Big-O for Nested Loops

Step 1: Analyze if it's a dependent loop or independent loop. Assume the counter variable of the outsider loop is `i`
1. if `i` is not involved in insider loop -> **independent loop**
2. Otherwise -> **dependent loop**

Step 2: If independent loop:
- O_overall = O(outsider loop) * O(insider loop)
- Otherwise (dependent loop):
	- For each iteration of the outsider loop -> count # of operations for the insider loop, add them together

## Nested Loop II - Dependent Loops

```
for(i=0; i<n; i=i+2){
	for(j=i; j<n; j++){
		x++;
	}
}
```

This is a dependent loop

|Iteration|Outsider Loop|Inner Loop Count|
|---------|-------------|----------------|
|1        |i=0          |n               |
|2        |i=2          |n-2             |
|3        |i=4          |n-4             |
|n/2      |i=n-1        |1               |

To determine the total number of iterations (let's call it x), add the values from the third column
- `x = n + (n-2) + (n-4) +...+ 1`
- Rewrite it as `x = 1 + 3 + 5 +...+ (n-2) + n`
- Rewrite again as `2x = (n+1) * (n/2)`
	- `x = ((n+1)*n)/4`
- Big-O notation simplified: O(x) = O(n^2)

## More Big-O Examples

```
for(i=0; i<n; i=i+n){
	x++;
}
```

- Only 4 steps of iteration
	- O(1) (easy level)

```
for(i=1; i<n; i=i*3){
	x++;
}
```

- Figute out how many steps of iteration:
	- iteration 1: i=1 (3^0)
	- iteration 2: i=3 (3^1)
	- iteration 3: i=9 (3^2)
	- iteration 4: i=27 (3^3)
	- iteration x: i=n (3^(x-1))

- 3^(x-1) = n -> x = log3(n)+1
	- O(x) = O(log(n))

```
for(i=0; i<n; i=i+3){
	f(); //f() is O(n^2)
}
```

- (n/3) iterations * O(n^2) = O(n^3)

```
for(i=0; i<n; i++){
	g(); //g() is O(log(n))
}

for(j=0; j<n; j++){
	x++;
}
```

- The first loop has n iterations
	- O(n) * O(log(n)) = O(nlog(n))
- The second loop has n iterations
	- O(n) * O(1) = O(n)
- The total big-O is O(nlog(n)) + O(n) = O(nlog(n))
	- O(n) is a lower term, so disregard

```
for(i=n; i>=1; i=i/3){
	for(j=0; j<n; j++){
		x++;
	}
}
```

- Notice: independent loops
- Outer loop: O(log(n))
- Inner loop: O(n)
- x++: O(1) (this step is sometimes ignored)
- O(log(n)) * O(n) * O(1) = O(nlog(n))

```
for(i=1; i<=n; i=i*2){
	for(j=1; j<=n; j=j+i){
		x++;
	}
}
```

- Notice: Dependent Loop

|Iteration|Outsider Loop|Inner Loop Count|
|---------|-------------|----------------|
|1        |i=1          |n               |
|2        |i=2          |n/2             |
|3        |i=4          |n/4             |
|4        |i=8          |n/8             |
|n        |i=n          |1               |

- Now we need to sum each row of the inner loop count column (call it x)
	- `x = n + (n/2) + (n/4) +...+ 1`
	- O(x) = `n[1+(1/2)+(1/4)+...+(1/n)]`
		- Eventually, O(n) (!) (that's pretty good)

## Common Big-O Complexity Classes

The following is listed from most to least efficient
- Constant O(1)
- Logarithmic O(log(n))
- Linear O(n)
- Log-Linear O(n)
- Quadratic O(n^2)
- Cubic O(n^3)
- Polynomial O(n^k)
- Exponential O(2^n) or O(k^n)
- Factorial O(n!)
- Anything worse than Exponential (actually, even quadratic) are considered pretty bad

---

[-> 04/13](04-13.md)