Exercise IIX
Consider the array data structure (i.e., Java's built-in array). Then, 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 $O(1)$:
- It takes a constant number of arithmetic operations to figure out where the element is located in the computer memory; the program knows the beginning of the array and the size of each element.
- Under the RAM model, it is "free" to access each memory location. In reality, it takes a constant time (a bounded time) to access each address in the computer memory.
- Since finding the address is $O(1)$, and retrieving the element in it is also $O(1)$, it gives you a total of $O(1)$.