Algorithmic Analysis

Algorithmic analysis is designed to compare two or more algorithms, independently of computer hardware capabilities and coding language.

Growth Function §

In order to analyse the runtime or storage of an algorithm, we must first make some assumptions:

• We define the basic operation, which is said to run with 1 unit of time.
• Any other operation can either be represented by the basic operation, or is treated to have negligible time.
• We use the Word RAM Model, which is a computational model. In it:
  • #todo https://youtu.be/lxfUXDobGZk?si=gxVqdQGBnqU2bKne&t=774

Then, we can start to model a function $f(n)$ which is the number of basic operations the algorithm takes for an input of size $n$. Note that ‘size’ $n$ can mean different things based on the input.

Restrictions on $f(n)$

Later, we shall be using limits and other mathematical tools involving the growth function $f(n)$. To make these easy, $f(n)$ has some restrictions:

• $n$ must be a natural number i.e. $n\in \mathbb{N}=\{1,2,3,\dots \}$
• It must be a positive function, i.e. all values of $f(n)>0$. Mathematically: $\forall n\in \mathbb{N},f(n)\ge 0$

Here are some common algorithms, as well as the basic operation used to analyse them:

Algorithm	Basic Operation	In Pseudocode
Sorting Algorithm	Key Comparision	if A[i] = A[j] then
Matrix Multiplication	Float/Int Multiplication	M[i][j] = a * b ...
Graph Algorithm	Visiting a node	Node i in G

Best, Worst and Average Case §

Furthermore, to have a holistic view on the algorithm, on it’s strengths and drawbacks, it helps to know how the algorithm will perform in the best-case scenario, where the input is in such a way that as little steps need to be performed, and worst-case scenario, where the maximum steps would most likely need to be performed.

Sorting Algorithms

In most sorting algorithms, at least one run through all the elements is required to check if the array is already sorted (which is the best case scenario). The worst case scenario, for most algorithms, is when the items are sorted in a descending order.

Average Case §

Average case analysis uses statistics and probably to find the expected running time of the algorithm, across all sizes of $n$. It is NOT an average of the best and worst case. For example, the average case of Linear Search Algorithm can be seen below:

Linear Search Average Case

Asymptotics §

Algorithmics analysis depends heavily on Asymptotics: