# Array - Interview Cake
04/01/2022 (Tuesday)

| - | Worst Case | - |
| -------- | -------- | -------- |
| space | O(n) | - |
| lookup | O(1) | - |
| append | O(1) | - |
| insert | O(n) | - |
| delete | O(n) | - |

## In-place Algorithm

* Destructive algorithm
* The original input is destroyed (or modified) during the function call.
* Without creating a new copy of the input
* Only create additional variables that are O(1) space

### Out-of-place
* Doesn’t make any changes that are visible to other functions.
* Those functions copy any data structures or objects before manipulating and changing them.

Working in-place is a good way to save time and space.
But, out-of-place algorithms are considered safer because they avoid side effects.

## Dynamic Array

* An array with automatic resizing

| | Average Case | Worst Case |
| -------- | -------- | -------- |
| space | O(n) | O(n) |
| lookup | O(1) | O(1) |
| append | O(1) | O(n) |
| insert | O(n) | O(n) |
| delete | O(n) | O(n) |

### Strengths
* Fast lookups
* Variable size
* Cache-friendly

### Weaknesses
* Slow worst-case appends
* Costly inserts and deletes

`We’d say the dynamic array’s size is 4 and its capacity is 10.`

### Doubling Appends

* Costs O(n) time!