Week 3. Analysis of Algorithms

Basic Analysis

Most algorithms transform input to output objects, the running time of an algorithm typically grows with the input size. We perform analysis of algorithms to understand how the running time grows with the input size.

Average case run time is often difficult to determine so we focus on the worst case running time: it is easier to analyse and crucial for fields such as games, finance and robotics.

We could determine these values experimentally but:

• it is necessary to implement the algorithm, which can be difficult
• we may have a number of potential algorithms for a given task but we only want to implement one
• results may not be indicative of the running time on other inputs not included in the experiment
• to compare algorithms, same software / hw has to be used

Theoretical Analysis

We can use a high-level description of the algorithm (pseudo-code) instead of an implementation which takes all inputs into account. We can evaluate the speed independent of any environment.

For any given algorithm, we determine a function $f(n)$ that characterises the worst-case scenario running time of the algorithm for the input size $n$.

Pseudo-code

Pseudo-code is a high-level description of an algorithm, it is less detailed than a program but more structured than just English. It is preferred for describing algorithms and hides program design issues.

Link to original

Random Access Machine Model

Random Access Machine Model

The Random Access Machine Model consists of:

• a CPU
• a memory; potentially unbounded bank of memory cells
• unit time; each CPU operation takes unit time; accessing any cell in memory takes unit time This is an approximation of real computers but mostly sufficient for predicting real running times.

Link to original

Primitive Operations

Primitive Operations

We can model primitive operations (assigning value to variable, comparing two values, evaluating expression, indexing into an array, following object reference, calling a method, and returning from a method) to take a constant amount of time.

Link to original

We can determine the maximum number of primitive operations by inspecting the pseudo-code of the algorithm:

def arrayMax(A, n):
	currentMax = A[0]         # 2
	for i = 1 to n - 1:       # 2n + 1
		if A[i] > currentMax: # 2(n - 1)
			currentMax = A[i] # 2(n - 1)
		{ i += 1 }            # 2(n - 1)
	return currentMax         # 1
                      # Total = 8n - 2

Estimating Running Time

Given the algorithm arrayMax executes $8n-2$ primitive operations in worst case. Let us define $a$ as the time taken by the fastest primitive operation, and $b$ be the time taken by the slowest primitive operation. Given $T(n)$ is the worst-case time:

• $a(8n-2)$ is the lower bound (fastest worst-case running time)
• $b(8n-2)$ is the upper bound (slowest worst-case running time) Hence we can also define $T(n)$ as bounded by two linear functions of $n$:

$$a(8n-2)\le T(n)\le b(8n-2)$$

Consider that $n\to 10n$, then the running time can be found: $T(10n)\approx 10\cdot T(n)$.

Growth Rate of Running Time

Changing the hardware / software environment affects $T(n)$ by a constant factor but does not alter the growth rate of $T(n)$. The linear growth rate of the running time $T(n)$ is an intrinsic property of the algorithm and is independent of hardware, implementation and computing environment.

We primarily consider seven functions:

• Constant: $1$
• Logarithmic: $\log n$
• Linear: $n$
• n Logarithmic: $n\log n$
• Quadratic: $n^2$
• Cubic: $n^3$
• Exponential: $2^n$

The growth rate is not affected by:

• constant factors: $10^{2}n+10^5$
• lower-order terms: $10^5{n}^2+10^{8}n$

Big-O Notation

Big-O Notation

The Big-O notation gives an upper bound on the growth rate of a function. Given functions $f(n)$ and $g(n)$, we say that $f(n)$ is $O(g(n))$, if there are positive constants $c$ and $n_0$ such that $f(n)\le c\cdot g(n)$ for $n\ge n_0$.

In general, if $f(n)$ is a polynomial of degree $d$ then $f(n)$ is $O(n^d)$.

• Drop lower-order terms.
• Drop constant factor in highest order term.

Examples:

• $2n+10$ is $O(n)$
• $7n-2$ is $O(n)$
• $3n^3+20n^2+5$ is $O(n^3)$
• $3\log n+5$ is $O(\log n)$

Link to original

The statement $\boxed{f(n)\text{ is }O(g(n))}$ means that the growth rate of $f(n)$ is not greater than the growth rate of $g(n)$. We can use Big-O notation to rank functions according to their growth rate.

	$f(n)$ is $O(g(n))$	$g(n)$ is $O(f(n))$
$g(n)$ grows more	Yes	No
$f(n)$ grows more	No	Yes
Same growth	Yes	Yes

Asymptotic Algorithm Analysis

Asymptotic Algorithm Analysis of an algorithm determines the running time in Big-O notation, to perform analysis:

• we find the worst-case number of primitive operations executed as a function of the input size
• we don’t need this function exactly, we just want to express it using Big-O

If we determine that the algorithm arrayMax executes at most $8n-2$ primitive operations then we say that the algorithm arrayMax “runs in $O(n)$ time”. Since constant factors and lower-order terms are eventually dropped, we can disregard them when counting primitive operations.

Link to original

Example: Computing Prefix Averages

We can demonstrate Asymptotic Algorithm Analysis with two algorithms for prefix averages.

The $i$-th prefix average of an array $X$ is the average of the first $(i+1)$ elements of $X$: $A[i]=(X[0]+X[1]+...+X[i])/(i+1)$.

For a sample array $X$, we see the data in $A$ to look like:

Computing the array $A$ of prefix averages of another array $X$ has applications in financial analysis.

Quadratic Implementation

The following algorithm computes prefix averages in quadratic time by directly applying the definition:

def prefixAverages(X, n):
	Input array X of n integers
	Output array A of prefix averages of X
	A = int[n]
	for i = 0 to n - 1:
		s = X[0]
		for j = 1 to i:
			s = s + X[j]
		A[i] = s / (i + 1)
	return A

The running time of prefixAverages is $2\cdot (1+2+...+n)+3n+2$ hence we have $O(1+2+...+n)$. The sum of the first $n$ integers is $1+2+...+n=\frac{n(n+1)}{2}$, hence we can say that prefixAverages runs in $O\left(\begin{array}{c}\frac{n(n+1)}{2}\end{array}\right)=O(n^2)$ time.

Linear Implementation

The following algorithm computes prefix averages in linear time by keeping a running sum.

def prefixAverages(X, n):
	Input array X of n integers
	Output array A of prefix averages of X
	A = new array of n integers
	s = 0
	for i = 0 to n - 1:
		s = s + X[i]
		A[i] = s / (i + 1)
	return A

Big-O and Relatives

There are three different notations we need to be aware of:

• Big-O where $f(n)$ is $O(g(n))$ if asymptotically $f(n)\le g(n)$.
• Big-Omega where $f(n)$ is $\Omega (g(n))$ if asymptotically $f(n)\ge g(n)$.

  Big-Omega

  Big-Omega defines $\boxed{f(n)\text{ is }\Omega (g(n))}$ if there is a constant $c>0$ and an integer constant $n_0\ge 1$ such that $f(n)\ge 1$ such that $f(n)\ge c\cdot g(n)$ for $n\ge n_0$.

  Link to original

• Big-Theta where $f(n)$ is $\Theta (g(n))$ if asymptotically $f(n)=g(n)$.

  Big-Theta

  Big-Theta defines $\boxed{f(n)\text{ is }\Theta (g(n))}$ if there is a constant $0<c^{\prime }<c^{\prime \prime }$ and an integer constant $n_0\ge 1$ such that $f(n)\ge 1$ such that $c^{\prime }\cdot g(n)\le f(n)\le c^{\prime \prime }\cdot g(n)$ for $n\ge n_0$.

  Link to original

Examples: