# Abstract Data Type

## What is a Data Structure?

A data structure is a way of organizing data so it can be used effectively.

## Why Data Structure?

- Essential ingredients in creating fast and powerful algorithm.
- Help to manage and organize data.
- Make code cleaner and easier to understand

## Abstract Data Type

- ADT is an abstraction of a data structure which provides only the interface to a data structure must adhere to.
- ADT does not give any specific details about how something should be implemented

### Example

Abstraction(ADT) | Implementation(DS) |
---|---|

List | Dynamic Array, Linked List |

Map | Tree Map, Hash Map |

Vehicle | Bicycle, Smart Car |

# Computational Complexity Analysis

## Complexity Analysis

- How many
**time**does this algorithm need to finish? - How many
**space**does this algorithm need for its computation?

## Big-O Notation

Big-O gives the upper bound of the complexity of worst case, helping to quantify performance as the input sie becomes arbitrarily large.

n = The size of the input

### Complexity Term

Complexity ordered in from smallest to largest

Term | Big-O Notation |
---|---|

Constant | $ O(1) $ |

Logarithmic | $ O(log(n)) $ |

Linear | $ O(n) $ |

Linearithmic | $ O(nlog(n)) $ |

Quadric | $ O(n^2) $ |

Exponential | $ O(b^3), b > 1 $ |

Factorial | $ O(n!) $ |

### Example

Let $f$ be a function that describes the running the time of a particular algorithm for an input of size n:

$ f(n) = 7log(n)^3+15n^2+2n^3 + 8 $

Complexity analysis only cares about the worst case, the complexity of $f(n)$ will be

$O(f(n)) = O(n^3)$

### More Examples

The following run in **linear** time: $O(n)$

$f(n) = n$

```
i := 0
While i < n Do
i = i + 1
```

$f(n) = n/3$

```
i := 0
While i < n Do
i = i + 3
```

The following run in **Quadric** time: $O(n^2)$

$f(n) = n*n = n^2$

```
For (i:=0; i < n; i = i + 1)
For (j:=0; j < n; j = j + 1)
```

Even change `j:=0`

to `j:=n`

, the complexity still remains.
If `i=0`

, we do `n`

work, If `i=1`

we do `n-1`

work, etc...

```
For (i:=0; i < n; i = i + 1)
For (j:=n; j < n; j = j + 1)
```

So the question becomes what is: $(n) + (n-1) + (n-2) + (n-3)+...+3+2+1 $

Turns out to be $O(n(n+1)/2) = O(n^2/2 + n/2) = O(n^2)$

Again, complexity analysis only cares about the worst case, so the complexity would be $O(n^2)$

This also a $O(n^2)$ example. $O(f(n)) = O(n*(3n+2n)) = O(n^2)$

```
i := 0
While i < n Do
j = 0
While j < 3*n Do
j = j + 1
j = 0
While j < 2*n Do
j = j + 1
i = i + 1
```

### Binary Search

Suppose we have a sorted array and we want to find the index of a particular value in the array, if it exists.

Time complexity below is $O(log(n))$.

```
low := 0
high := n - 1
While low <= high Do
mid := (low + high) / 2
If array[mid] == value: return mid
Else If array[mid] < value: low = mid + 1
Else If array[mid] > value: high = mid - 1
return -1
```