---
# System prepended metadata

title: Array - Interview Cake

---

# 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!





















