Big-O notation is a mathematical concept commonly utilized to describe the limiting behaviour of functions with very large inputs. Formally, it can be defined as follows:

is said to be in if there exist a real number and a natural number such that , for all .

Alternatively, .

Example

Variants

Big Omega Notation

Big omega notation written as can effectively be thought of as the inverse of big-O notation as it is usually defined as .

Alternatively, it can be defined independently from Big-O notation as follows

is said to be in if there exist a real number and a natural number such that , for all .

Alternatively, .

Example

Big Theta Notation

Big theta notation written as is a method for describing both the upper and lower limits of a function, and is usually defined as .

Alternatively, it can be defined independently from Big-O notation as follows

is said to be in if there exist two a real numbers and and a natural number such that , for all .

Alternatively, .

Example

In computer science big-O notation describes a generalization of the mathematical big-O notation to computer programs and is used to describe their behaviour with large input sizes.

General Rules

• Single operations: constant time
• Consecutive operations: sum operation times
• Conditionals: condition check time plus branch time (which branch?)
• Loops: sum of loop body times
• Function call: time for function

For Loop Executions

Loops don't always take a single iteration approach where the integer starts at and loops till , instead when the loop iterates differently we can use the following steps to determine it's execution pattern:

1. Determine the "range" of the loop variable
2. Determine how many elements within that range will be "hit"

Examples

Simple Example

int findInd(vector<int>& arr, int q) {
	for (int i = 0; i < arr.size(); i++) {
		if (arr[i] == q) return i;
	}
	
	return -1;
}

Treating , and treating assignments, comparisons, and external function calls as constant time operations we can determine the worst case runtime of this program to be .

We arrive at this conclusion as all our operations are treated as constant time operations (thus only adding or multiplying by constants), and our for loop grow proportionally to our input size .

Nested Iterations

bool hasDuplicate(int arr[], int size) {
	for (int i = 0; i < size-1; i++) {
		for (int j = i+1; j < size; j++) {
			if (arr[i] == arr[j]) return true;
		}
	}
	
	return false;
}

Treating , and again treating assignments, comparisons, and external function calls as constant time operations we can determine the worst case runtime of this program to be .

This can be determined by again looking at the for loops we can see that in the worst case scenario the first for loop is run from 0 to size-1, and the internal loop from 1 to size-1, additionally, we can see that every time the first for loop is run the nested one runs as well, meaning we can multiply the time demands, giving us and thus .

Non-Trivial Iterators

Example 1

void candyApple(int n) {
	for (int i = 1; i < n; i *= 3) {
		cout << "iteration: " << i << endl;
	}
}

Here, the loop variable i starts at 1 and is multiplied by 3 every iteration. That means the number of iterations is the largest integer such that:

Taking logarithms:

So the runtime grows proportionally to , as we can ignore the base of the logarithm in big-O notation.

Example 2

void caramelCorn(int n) {
	for (int i = 0; i * i < 6 * n; i++) {
		cout << "iteration: " << i << endl;
	}
}

Here, the loop condition is i * i < 6n. The loop continues until , which means:

So the number of iterations is proportional to (the constant factor doesn’t matter asymptotically):

An array is a data structure which contains a "collection" of elements.

Data Allocation

Array data can either be allocated static or dynamic, depending on how the constituting variables are initialized.

Static

Example

int data[] = {1, 2, 3, 4, 5};

printf("%d", data[0]); // 1
printf("%d", data[3]); // 4

Dynamic

Example

int *data = malloc(sizeof(int) * 5)

data[0] = 1;
data[1] = 2;
data[2] = 3;
data[3] = 4;
data[4] = 5;

printf("%d", data[0]); // 1
printf("%d", data[3]); // 4

free(data);

Loop invariants are properties of the algorithm or structure that are always true at particular points in the program. Within a loop's body these properties may become violated briefly, but the rest of the loop's instructions fix these properties for the next iteration.

Loop invariants are used in an inductive proof to formally validate the "correctness" of an algorithm. For a loop invariant to be used in a proof features of the code being analyzed must be used to demonstrate that any violations of the loop invariant are restored before the next iteration.

Determining the Loop Invariant

To determine the loop invariant we can roughly follow these steps

1. Analyze what the code does
   • Read through the instructions and determine roughly what it's purpose is
2. Start with a concrete example
   • Run through the function with an example input
3. Suppose we pause somewhere in the middle of the loop
   • What can we determine about the state of the local variables

Proving a Loop Invariant

1. Induction variable:
   • Number of times through the loop
2. Base case:
   • Prove the invariant holds before the loop starts
3. Induction hypothesis:
   • Assume the invariant holds before beginning some (unspecified) loop iteration
4. Inductive step:
   • Prove the invariant holds at the end of the iteration, ready for the next iteration
5. Termination:
   • Make sure the invariant implies correctness when the loop ends

Example

int minIndex(vector<int>& arr, int a) {
	int m = a;
	
	for (int i = a+1; i < arr.size(); i++) {
		if (arr[i] < arr[m]) {
			m = i;
		}
	}
	
	return m;
}

Firstly, we can read through the code and see that it only updates m to be the current index if the element at the current index is smaller than the element at the index m. We can roughly determine then that our exampleFunction returns the index smallest element after a, or a if the element at a is the smallest already.

Running through a few examples we can see that m is always the index of the smallest element of the processed array so far.

Loop Invariant: m is the index of the minimum element in the arr[a..i-1] at the start of the iteration i for all

Base Case: i=a+1

• Before the first iteration of the loop, the invariant states that m contains the index of the smallest element of arr[a..a]
• This is set explicitly by the line int m = a;
• Therefore the loop invariant must hold in the base case

Inductive Step: i = k, a + 1 <= k < arr.size()

• Assume the loop invariant holds prior to processing index k, ie. m contains the index of the smallest element of arr[a..k-1]
• Case 1: arr[k] < arr[m]
  • By assumption, arr[k] is smaller than any element of arr[a..k-1]
  • m is set to k, and contains the index of the smallest element of arr[a..k], thus loop invariant holds after processing index k
• Case 2: `arr[k] >= arr[m]
  • By assumption, arr[k] is not smaller than the smallest element of arr[a..k-1]
  • No action is taken, and m contains the index of the smallest element of arr[a..k], thus the loop invariant holds after processing index k

Termination: i=arr.size()

• Invariant property states that m contains the index of the smallest element of arr[a..arr.size()-1]
• This range describes the entire subarray from a to arr.size()-1
• Therefore at termination, m contains the index of the smallest element in the entire subarray
• Since arr.size() is finite, and i increments each iteration towards arr.size() the program must terminate.

A linked list is a type of dynamic data structure that consists of nodes linked together. Each node contains two parameters, data and the address of the next node.

Properties

Head

The head is a property of a linked list that represents the first node in the list. When accessing elements the head node is the first one (ie arr.get(0)).

Tail

The tail is a property of a linked list that represents the last node in the list.

Abstract Data Type

We can define a linked list abstractly as follows:

template <class T>  
struct Node {  
	T data;  
	Node * next;  

	Node(LIT ndata, Node * nx=nullptr): data(ndata),next(nx) {}  
};

template <class T>
struct LinkedList {
	private:
		Node* head;
		Node* tail;
		
		int length;
		
	public:
	 LinkedList();
	 
	// ... Ommited
}

Auxiliary Operations

Traversing a Linked List

To traverse a linked list maintain a pointer to the current node dereferencing it each iteration, if the next parameter of the node is NULL, the whole linked list has been traversed, otherwise update the pointer to the current node to be the next parameter.

Example

void iterateLinkedList(Node<int>* startingNode) {
	Node<int>* p = startingNode;
	
	while (p->next != nullptr) {
		std::cout << p->data << std::endl;
	
		p = p->next;
	}
}

Inserting into a Linked List

To insert into a linked list maintain a pointer to the node to insert, and a pointer to the node before and after the node to insert, then just set the next parameter of the node before to be the address of the node to insert, and the next parameter of the node to insert to be the node after the node to insert.

Example

void insertNodeIntoLinkedList(
	Node<int>* previousNode,
	Node<int>* nextNode,
	Node<int>* newNode
) {
	previousNode->next = newNode;
	newNode->next = newNode;
}

Deleting from a Linked List

To delete from a linked list set the previous node's next to be the node after the one to delete, and then free the memory of the node to delete

Example

void deleteNodeFromLinkedList(
	Node<int>* previousNode,
	Node<int>* nodeToDelete,
	Node<int>* nextNode
) {
	previousNode->next = nextNode;

	delete nextNode;
}

Time Complexity

Without Tail Pointer

A linked list is a variation of the singly linked list where each node also contains a pointer to it's previous node as well as it's next node. This additional reference can introduce performance improvements for insertions and deletions at the cost of additional memory.

Time Complexity

Insertion sort is a simple sorting algorithm which starts by splitting the input array into two parts, a sorted part and an unsorted part, the sorted part bigger than the first element in the unsorted part is then shifted forwards one spot until there's a spot for the first element of the unsorted part to be placed within the sorted part.

// Assumes arr[0..p-1] are in sorted order
void slide(vector<int>& arr, int p) {
	int temp = arr[p];
	int j = p;
	
	while (j > 0 && arr[j-1] > temp) {
		arr[j] = arr[j-1];
		
		j--;
	}
	
	arr[j] = temp;
}

void insertionSort(vector<int>& arr) {
	for (int i = 0; i < arr.size(); i++) {
		slide(arr, i);
	}
}

Analysis

Runtime Complexity

Looking at the two loops, we can see that the first loop always iterates from 0 to arr.size(), the inner function on the other hand iterates backwards from i to 0. Using this knowledge we can construct a formula for the runtime

where = arr.size()

Correctness

Loop Invariant: Before iteration i of the for loop, arr[0..i-1] contains the i smallest elements of arr in ascending order.

Base Case: i = 0

• Before executing the iteration for i=0, the invariant states that arr[0..-1] contains the 0 smallest elements of arr in ascending order.
• Since the interval arr[0..-1] contains no elements the invariant holds in the base case. Inductive Step: i = k, 0 ≤ k < arr.size()
• Assume the loop invariant holds prior to processing index k, i.e. arr[0..k-1] contains the k smallest elements of arr in ascending order.
• Calling slide(arr, k) requires arr[0..k-1] to be sorted, which is guaranteed by the invariant.
• From the proof of slide, we know that afterwards arr[0..k] is sorted.
• Thus after processing index k, arr[0..k] contains the k+1 smallest elements of arr in ascending order and the loop invariant holds. Termination: i = arr.size()
• Invariant property states that arr[0..arr.size()-1] contains the arr.size() smallest elements of arr in ascending order.
• This interval contains the entire array, and thus the entire array is now in sorted order.
• Since arr.size() is finite, and i increments each iteration towards arr.size(), the program must terminate.

Merge sort is a sorting algorithm that uses a divide-and-conquer approach to sort an array. The algorithm works by recursively dividing the array into two halves until each subarray contains only one element, then merging these subarrays back together in sorted order.

void mergeSort(vector<T>& arr) {
	mergeSortRecursive(arr, 0, arr.size() - 1);
}

void mergeSortRecursive(vector<T>& arr, int low, int high) {
	if (low >= high) return;
	
	int mid = (low + high) / 2;
	
	// Sort the left half
	mergeSortRecursive(arr, low, mid);
	
	// Sort the right half
	mergeSortRecursive(arr, mid + 1, high);
	
	// Merge the sorted halves
	merge(arr, low, mid, high);
}

void merge(vector<T>& arr, int low, int mid, int high) {
	vector<T> temp;
	
	int a = low,
	    b = mid + 1;
	    
	for (int k = low; k <= high; k++) {
		if (a <= mid && (b > high || arr[a] < arr[b])) {
			temp.push_back(arr[a++]);
			
			continue;
		}
		
		temp.push_back(arr[b++]);
	}
	
	for (int k = low; k <= high; k++) {
		arr[k] = temp[k - low];
	}
}

Analysis

Runtime Complexity

We can notice that at every recursion step the sub arrays are divided into two equally sized sub arrays each of length .

This means that for each level of recursion, the work performed on each totals where is the length of the array and is the cost to merge the elements of the array. Considering the array is split in half on each operation we can see that the number of levels of recursion is in the order of as the array is halved each iteration ().