## Outline
- Concept
	- Data Structure
	- Code Efficiency
- Big-O

## What is Data Structure?

- How data is organized in memory (or on disk)

|Data|Structure|
|----|---------|
|Atomic or composite data|A set of rules that holds the data together|

- Examples:
	- Linked List
	- Array

## Why do we care about Data Structure?

- Efficiency can refer to either 
	- Space (importance depending on architecture)
	- or Time
- We will focus on **time**, So, we want our operations efficient in terms of time

## How to measure efficiency?

- Wall-clock time?
	- Not so great
		- Not that accurate
		- can't compare across computer or programmers
		- dependent on circumstances and what's running

- Count the number of operations!

### What kind of Operations?

- insert (add)
- delete (remove)
- access/retrieval
- min/max
- union/merge (less common)

## A Simple Example

- We assume each basic operation takes one step
- Example: Initialize an array (a loop setting `a[i]=0`)
- Count the steps ... how many times is ...

Using a for loop:
```
for(i = 0; i<n; i++){
	a[i] = 0;
}
```
- Break down the steps:
	1. `i = 0` (done once)
	2. `i < n` (done 'n+1' times)
	3. `a[i] = 0` (done 'n' times)
	4. `i++` (done 'n' times)
- The total number of steps is `1 + (n+1) + n + n` = `3n+2`

- This is tedious and error prone, so we will teach how to count and be lazy!

## When do we care?

- Turns out we care about what happens **when n is big**, i.e., how our alogirthm behaves as n gets large

- When n is a million, 2 doesn't matter, 2000 doesn't matter, c doesn't matter for sufficiently larger n

- We only care about the one with the highest impact on efficiency

## Big-O Notation

- To classify the cost of an algorithm we use the big-O notation
	- it's called that because we use a capital 'O'

- To compute the big-O runtime of a function (mathematical function):
	- drop all but the fastest-growing term
	- drop any coefficient on that remaining term
- So, e.g., `3n+2` is O(n)
	- Drop the 2 (not the fastest growing term) and the 3 (coefficient of remaining term)

- Example: `5n^2 + 3n + 5` -> `5n^2` -> `n^2`
	- Would be represented as O(n^2)

- Example: `600 + 30n` -> `30n` -> `n`
	- Would be represented as O(n)

- Example: `15n + 12nlog(n) + 3` -> `12nlog(n)` -> `nlog(n)`
	- Would be represented as O(nlog(n))

- Example: `14n^2 + 0.05n^3 + 18000000` -> `0.05n^3` -> `n^3`
	- Would be represented as O(n^3)

## Apply Big-O on Code Analysis

- Let's analyze some loops and compute the big-O runtimes
	- `for(i=0; i<n; i++) x++;`
		- `3n+2` -> `n` -> O(n)
	- `for(i=n; i>0; i--) x++;`
		- O(n)
	- `for(i=0; i<(n/2); i++) x++;`
		- cut the threshold by half
		- O(n/2) is **not** the finalized runtime
		- O(n) is the finalized runtime
	- `for(i=0; i<n; i=i+2) x++;`
		- Double the step size
		- O(n/2) is **not** the finalized runtime
		- O(n) is the finalized runtime

## Big-O Add

- O(n) + O(n) = ?
	- `for(i=0; i<n; i++) x++; O(n)`
	- `for(i=0; i<n; i++) x++; O(n)`
	- O(n) + O(n) = O(n + n) = O(2n) -> O(n)

- `for(i = 1; i < n; i=i*2) x++`
	- Break it down:
		- iteration 1: i=1
		- iteration 2: i=2
		- iteration 3: i=4
		- iteration 4: i=8
		- iteration 5: i=16
		- and so on, until i<n
		- Notice: iteration x: i=2^(x-1)
	- The total number of iterations we need to run is x = (log2(n)+1)
		- O(x) = O(log2(n)+1) -> O(log2(n)) -> O(log(n))
			- log base value doesn't matter

- Example: `for(i=1; i<n; i=i*100) x++;`
	- O(log100(n)) -> O(log(n))
- Example: `for(i=1; i<n; i=i/5) x++;`
	- O(log(n))

Example: Nested For Loop

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

- How many times does this need to run?

|iteration number|outer loop|inner loop|
|----------------|----------|----------|
|1               |i=0       |n         |
|2               |i=1       |n         |
|3               |i=2       |n         |
|n               |i=n-1     |n         |

- You get O(n * n) = O(n^2)
	- Essentially, you multiply a big-O (outer loop) by another big-O (inner loop)

Example: Another Nested For Loop

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

- These loops are no longer independent

|iteration number|outer loop|inner loop|
|----------------|----------|----------|
|1               |i=1       |0         |
|2               |i=2       |1         |
|3               |i=3       |2         |
|n               |i=n       |n-1       |

- Total number of iterations is x = 0+1+2+...+(n-1)
- What is x?
	- x = (n-1)+(n-2)+...+2+1+0
	- 2x = (n-1)\*n -> x = ((n-1)\*n)/2
- O(x) = O(((n-1)\*n)/2) -> O(n^2)