Exercise IIX
Consider the array data structure (i.e. Java's built-in array). We define the following operations:
- insert front: insert an element to the front of an array (prepend the array). This is not updating the value of an existing element.
- insert middle: insert an element at a random index $i$ where $0 < i < \text{length} - 1$
- insert back: insert an element to the end of the array (append the array). assume array has enough capacity.
- corresponding delete operations (delete front, delete middle, delete back).
- access: read an element at a random index.
Exercise Based on your understanding of the array data structure, complete the following table. Use Big-Oh notation for expressing asymptotic runtime.
| Operation | Asymptotic runtime |
|---|---|
| insert front | |
| insert middle | |
| insert back | |
| delete front | |
| delete middle | |
| delete back | |
| access |
Solution
| Operation | Asymptotic runtime |
|---|---|
| insert front | $O(n)$ — shift all elements to right to make room for new one |
| insert middle | $O(n)$ — shift elements to make a gap |
| insert back | $O(1)$ — insert at arr[numElements] |
| delete front | $O(n)$ — shift all elements to left to fill the gap |
| delete middle | $O(n)$ — shift elements to fill a gap |
| delete back | $O(1)$ — decrement numElements |
| access | $O(1)$ — performs constant # arithmetic operations! |
Accessing an element at a given position is done in $O(1)$ because it takes a constant number of arithmetic operations to figure out where the element is located in the computer memory (since the program knows the beginning of the array and the size of each element). It takes a constant time (or to be more exact, a bounded time) to access each address in the computer memory, and since finding the address is $O(1)$, and retrieving the element in it is also $O(1)$, it gives you total of $O(1)$.