Array

Arrays are data structures that store multiple data types in a contiguous block of memory. Arrays are implemented in almost all low-level programming languages as the default way to store other data types. They provide fast access to elements but (with the exception of dynamic arrays) cannot have it’s size changed.

Properties §

• A data structure with a set length
• Items are accessed via their index, which is a number that stores their location. They are usually 0-indexed, which means the index starts from 0 (instead of 1)
• They are static (a fixed size) (not to be confused with static in OOP). Specifically, their length cannot be changed once initialised.
• Items are added to arrays by overwriting previous value via index, or by swapping elements.

ADT Signature §

name: Array
import: element,int,bool
ops:
	newArray: int → Array
	append: Array x element x int → Array
	get: Array x int  → element
	isEmpty/isFull: Array → bool
	length: Array → int

Time Complexity Analysis §

Basic Operation: Array access

Assumptions:

• $A$ = The array itself
• $n$ = Elements in array
• $c$ = Capacity (storage of the array)
• $0\le i<c$: The index $i$ is a valid index.

Unsorted §

Operation	Worst Case (WC)	Best Case (BC)	Average Case (AC)	Case descriptions
Access an element at index $i$	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Basic operation
Insert an element $x$ at index $i$, assuming there is space	$\Theta (1)$	$\Theta (1)$		WC ($i<n$): Increase $n$ by 1, and set $A[n]=A[i]$. Then insert the element by setting $A[i]=x$ BC ($i\ge n$): Inserting at index $n$ or higher involves no shifting
Delete an element at index $i$ (via overwriting )	$\Theta (1)$	$\Theta (1)$		WC ($i<n$): Swap the last element $A[n-1]$ with $A[i]$, then decrement $n$ by 1 BC ($i=n-1$): Decrement $n$ by 1.
Searching for an element $x$ (assuming comparison is $O(1)$)	$\Theta (n)$	$\Theta (1)$	$\Theta (n)$	WC ($A[n-1]=x$ or $x$ not in array): Have to Linear search through array BC ($A[0]==x$): One comparison at the first element AC ($A[0\dots n-1]=x$): See average case derivation

Sorted §

Operation	Worst Case (WC)	Best Case (BC)	Average Case (AC)	Case descriptions
Access an element at index $i$	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Basic operation
Insert an element $x$	$O(n)$	$\Theta (1)$		WC ($x$ is not the largest element) : Various methods exist: 1. Modified binary search that returns the index of greatest element lesser than $x$, then shift all elements to right by 1, then insert. 2. Add to the end, then use insertion sort, which runs well when there are few unsorted elements. BC ($x$ is the largest element) : Insert at $A[n]$, increment $n$ after
Delete an element at index $i$	$O(n)$	$\Theta (1)$		WC ($i=0$): Need to shift $n-1$ elements to the right by one using element swaps. BC ($i=n-1$): Decrement $n$ by 1
Searching for an element $x$ (assuming comparison is $O(1)$)	$\Theta (\log (n))$	$\Theta (1)$		See Binary Search Algorithm

Implementation §

Most Programming Languages store arrays as references to memory locations. That is, if we create an array, simply trying to assign it to something else will copy the reference, not the value:

In Java §

#todo

{} is the syntax to for new int[] {3,3,5,5} creates a new unique array.