• Running Time
• Empirical Analysis
• Theoretical Analysis
• Pseudocode
• The Abstract RAM Model
• Primitive Operations
• Counting Primitive Operations
• Estimating Running Times
• Big-Oh Notation
• Asymptotic Analysis of Algorithms
• Example: Computing Prefix Averages
• Example: Binary Search
• Math Needed for Complexity Analysi
• Relatives of Big-Oh
• Complexity Classes
• Generate and Test Algorithms
• Example: Subset Sum
• Summary

❖ Running Time

An algorithm is a step-by-step procedure for solving a problem in a finite amount of time Most algorithms map input to output running time typically grows with input size average time often difficult to determine Focus on worst case running time easier to analyse crucial to many applications: finance, robotics, games, …

❖ Empirical Analysis

Write program that implements an algorithm Run program with inputs of varying size and composition Measure the actual running time Plot the results

❖ ... Empirical Analysis

Limitations:

• requires to implement the algorithm, which may be difficult

• results may not be indicative of running time on other inputs

• same hardware and operating system must be used in order to compare two algorithms

❖ Theoretical Analysis

• Uses high-level description of the algorithm instead of implementation ("pseudocode")

• Characterises running time as a function of the input size, n

• Takes into account all possible inputs

• Allows us to evaluate the speed of an algorithm independent of the hardware/software environment

❖ Pseudocode

• More structured than English prose

• Less detailed than a program

• Preferred notation for describing algorithms

• Hides program design issues

❖ ... Pseudocode

Example: Find maximal element in an array

arrayMax(A):
|  Input  array A of n integers
|  Output maximum element of A
|
|  currentMax=A[0]
|  for all i=1..n-1 do
|  |  if A[i]>currentMax then
|  |     currentMax=A[i]
|  |  end if
|  end for
|  return currentMax

❖ ... Pseudocode

❖ Exercise : Pseudocode

Formulate the following verbal description in pseudocode:

In the first phase, we iteratively pop all the elements from stack S and enqueue them in queue Q, then dequeue the element from Q and push them back onto S.

As a result, all the elements are now in reversed order on S.

In the second phase, we again pop all the elements from S, but this time we also look for the element x.

By again passing the elements through Q and back onto S, we reverse the reversal, thereby restoring the original order of the elements on S.

Sample solution:

while empty(S) do
   pop e from S, enqueue e into Q
end while
while empty(Q) do
   dequeue e from Q, push e onto S
end while
found=false
while empty(S) do
   pop e from S, enqueue e into Q
   if e=x then
      found=true
   end if
end while
while empty(Q) do
   dequeue e from Q, push e onto S
end while

❖ Exercise : Pseudocode

1. int temp = A[i];
   A[i] = A[j];
   A[j] = temp;
   

2. NodeT *succ = head->next;
   head->next = succ->next;
   succ->next = head;
   head = succ;
   

3. x = StackPop(S);
   y = StackPop(S);
   StackPush(S, x);
   StackPush(S, y);
   

The following pseudocode instruction is problematic. Why?

...
swap the two elements at the front of queue Q
...

❖ The Abstract RAM Model

RAM = Random Access Machine

• A CPU   (central processing unit)
• A potentially unbounded bank of memory cells
  • each of which can hold an arbitrary number, or character
• Memory cells are numbered, and accessing any one of them takes CPU time

❖ Primitive Operations

❖ Counting Primitive Operations

arrayMax(A):
|  Input  array A of n integers
|  Output maximum element of A
|
|  currentMax=A[0]                   1
|  for all i=1..n-1 do               n+(n-1)
|  |  if A[i]>currentMax then        2(n-1)
|  |     currentMax=A[i]             n-1
|  |  end if
|  end for
|  return currentMax                 1
                                     -------
                             Total   5n-2

❖ Estimating Running Times

Algorithm arrayMax requires 5n – 2 primitive operations in the worst case

• best case requires 4n – 1 operations   (why?)

Define:

• a … time taken by the fastest primitive operation
• b … time taken by the slowest primitive operation

Let T(n) be worst-case time of arrayMax. Then

   a·(5n - 2) ≤ T(n) ≤ b·(5n - 2)

Hence, the running time T(n) is bound by two linear functions

❖ ... Estimating Running Times

Seven commonly encountered functions for algorithm analysis

• Constant ≅ 1
• Logarithmic ≅ log n
• Linear ≅ n
• N-Log-N ≅ n log n
• Quadratic ≅ n²
• Cubic ≅ n³
• Exponential ≅ 2ⁿ

❖ ... Estimating Running Times

In a log-log chart, the slope of the line corresponds to the growth rate of the function

See the following chart :
http://bigocheatsheet.com/

❖ ... Estimating Running Times

The growth rate is not affected by constant factors or lower-order terms Examples: 102n + 105 is a linear function 105n2 + 108n is a quadratic function

❖ ... Estimating Running Times

Changing the hardware/software environment

• affects T(n) by a constant factor
• but does not alter the growth rate of T(n)

⇒ Linear growth rate of the running time T(n) is an intrinsic property of algorithm arrayMax

❖ Exercise : Estimating running times

Determine the number of primitive operations

matrixProduct(A,B):
|  Input  n×n matrices A, B
|  Output n×n matrix A·B
|
|  for all i=1..n do
|  |  for all j=1..n do
|  |  |  C[i,j]=0
|  |  |  for all k=1..n do
|  |  |     C[i,j]=C[i,j]+A[i,k]·B[k,j]
|  |  |  end for
|  |  end for
|  end for
|  return C

❖ Exercise : Estimating running times

matrixProduct(A,B):
|  Input  n×n matrices A, B
|  Output n×n matrix A·B
|
|  for all i=1..n do                     2n+1
|  |  for all j=1..n do                  n(2n+1)
|  |  |  C[i,j]=0                        n2
|  |  |  for all k=1..n do               n2(2n+1)
|  |  |     C[i,j]=C[i,j]+A[i,k]·B[k,j]  n3·5
|  |  |  end for
|  |  end for
|  end for
|  return C                              1
                                         ------------
                                 Total   7n3+4n2+3n+2

❖ Big-Oh Notation

Given functions f(n) and g(n), we say that

if there are positive constants c and n₀ such that

❖ ... Big-Oh Notation

Example: function 2n + 10 is O(n) 2n+10 ≤ c·n ⇒   (c-2)n ≥ 10 ⇒   n ≥ 10/(c-2) pick c=3 and n0=10

❖ ... Big-Oh Notation

Example: function n2 is not O(n) n2 ≤ c·n ⇒   n ≤ c inequality cannot be satisfied since c must be a constant

❖ Exercise : Big-Oh

Show that

1. 7n-2 is O(n)
2. 3n³ + 20n² + 5 is O(n³)
3. 3·log n + 5 is O(log n)

1. 7n-2 is O(n)
   need c>0 and n₀≥1 such that 7n-2 ≤ c·n for n≥n₀
   ⇒  true for c=7 and n₀=1
2. 3n³ + 20n² + 5 is O(n³)
   need c>0 and n₀≥1 such that 3n³+20n²+5 ≤ c·n³ for n≥n₀
   ⇒  true for c=4 and n₀=21
3. 3·log n + 5 is O(log n)
   need c>0 and n₀≥1 such that 3·log n+5 ≤ c·log n for n≥n₀
   ⇒  true for c=8 and n₀=2

❖ Big-Oh and Rate of Growth

• Big-Oh notation gives an upper bound on the growth rate of a function
  • "f(n) is O(g(n))" means growth rate of f(n) no more than growth rate of g(n)
• use big-Oh to rank functions according to their rate of growth

❖ Big-Oh Rules

• If f(n) is a polynomial of degree d   ⇒ f(n) is O(n^d)
  • lower-order terms are ignored
  • constant factors are ignored
• Use the smallest possible class of functions
  • say "2n is O(n)" instead of "2n is O(n²)"
• Use the simplest expression of the class
  • say "3n + 5 is O(n)" instead of "3n + 5 is O(3n)"

❖ Exercise : Big-Oh

Show that   `sum_(i=1)^n i`   is O(n²)

`sum_(i=1)^ni = (n(n+1))/2 = (n^2+n)/2`

which is O(n²)

❖ Asymptotic Analysis of Algorithms

Asymptotic analysis of algorithms determines running time in big-Oh notation:

• find worst-case number of primitive operations as a function of input size
• express this function using big-Oh notation

Example:

• algorithm arrayMax executes at most 5n – 2 primitive operations
  ⇒  algorithm arrayMax "runs in O(n) time"

Constant factors and lower-order terms eventually dropped
⇒ can disregard them when counting primitive operations

❖ Example: Computing Prefix Averages

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

NB. computing the array A of prefix averages of another array X has applications in financial analysis

❖ ... Example: Computing Prefix Averages

A quadratic alogrithm to compute prefix averages:

prefixAverages1(X):
|  Input  array X of n integers
|  Output array A of prefix averages of X
|
|  for all i=0..n-1 do          O(n)
|  |  s=X[0]                    O(n)
|  |  for all j=1..i do         O(n2)
|  |     s=s+X[j]               O(n2)
|  |  end for
|  |  A[i]=s/(i+1)              O(n)
|  end for
|  return A                     O(1)

⇒ Time complexity of algorithm prefixAverages1 is O(n²)

❖ ... Example: Computing Prefix Averages

The following algorithm computes prefix averages by keeping a running sum:

prefixAverages2(X):
|  Input  array X of n integers
|  Output array A of prefix averages of X
|
|  s=0
|  for all i=0..n-1 do          O(n)
|     s=s+X[i]                  O(n)
|     A[i]=s/(i+1)              O(n)
|  end for
|  return A                     O(1)

Thus, prefixAverages2 is O(n)

❖ Example: Binary Search

The following recursive algorithm searches for a value in a sorted array:

search(v,a,lo,hi):
|  Input  value v
|         array a[lo..hi] of values
|  Output true if v in a[lo..hi]
|         false otherwise
|
|  mid=(lo+hi)/2
|  if lo>hi then return false
|  if a[mid]=v then
|     return true
|  else if a[mid]<v then
|     return search(v,a,mid+1,hi)
|  else
|     return search(v,a,lo,mid-1)
|  end if

❖ ... Example: Binary Search

Successful search for a value of 8:

❖ ... Example: Binary Search

Unsuccessful search for a value of 7:

❖ ... Example: Binary Search

Cost analysis:

• C_i = #calls to search() for array of length i
• for best case, C_n = 1
• for a[i..j], j<i (length=0)
  • C₀ = 0
• for a[i..j], i≤j (length=n)
  • C_n = 1 + C_n/2   ⇒ C_n = log₂ n

Thus, binary search is O(log₂ n) or simply O(log n)   (why?)

❖ ... Example: Binary Search

❖ Math Needed for Complexity Analysi

Summations Logarithms logb (xy) = logb x + logb y logb (x/y) = logb x - logb y logb xa = a logb x logb a = logx a / logx b	Exponentials a(b+c) = abac abc = (ab)c ab / ac = a(b-c) b = alogab bc = ac·logab
Proof techniques Summation   (addition of sequences of numbers) Basic probability   (for average case analysis, randomised algorithms)

❖ Exercise : Analysis of Algorithms

What is the complexity of the following algorithm?

splitList(L):
|  Input  non-empty linked list L
|  Output L split into two halves
|
|  // use slow and fast pointer to traverse L
|  slow=head(L), fast=head(L).next
|  while fast≠NULL ∧ fast.next≠NULL do
|     slow=slow.next, fast=fast.next.next  // advance pointers
|  end while
|  cut L between slow and slow.next

Answer: O(|L|)

❖ Exercise : Analysis of Algorithms

What is the complexity of the following algorithm?

binaryConversion(n):
|  Input  positive integer n
|  Output binary representation of n on a stack
|
|  create empty stack S
|  while n>0 do
|  |  push (n mod 2) onto S
|  |  n=n/2
|  end while
|  return S

Assume that creating a stack and pushing an element both are O(1) operations   ("constant")

Answer: O(log n)

❖ Relatives of Big-Oh

big-Omega

• f(n) is Ω(g(n)) if there is a constant c > 0 and an integer constant n₀ ≥ 1 such that
  f(n) ≥ c·g(n)    ∀n ≥ n₀

big-Theta

• f(n) is Θ(g(n)) if there are constants c',c'' > 0 and an integer constant n₀ ≥ 1 such that
  c'·g(n) ≤ f(n) ≤ c''·g(n)    ∀n ≥ n₀

❖ ... Relatives of Big-Oh

• f(n) is O(g(n)) if f(n) is asymptotically less than or equal to g(n)
• f(n) is Ω(g(n)) if f(n) is asymptotically greater than or equal to g(n)
• f(n) is Θ(g(n)) if f(n) is asymptotically equal to g(n)

❖ ... Relatives of Big-Oh

Examples:

• ¼n² is Ω(n²)
  • need c > 0 and n₀ ≥ 1 such that ¼n² ≥ c·n² for n≥n₀
  • let c=¼ and n₀=1
• ¼n² is Ω(n)
  • need c > 0 and n₀ ≥ 1 such that ¼n² ≥ c·n for n≥n₀
  • let c=1 and n₀=2
• ¼n² is Θ(n²)
  • since ¼n² is in Ω(n²) and O(n²)

❖ Complexity Classes

Problems in Computer Science …

• some have polynomial worst-case performance (e.g. n²)
• some have exponential worst-case performance (e.g. 2ⁿ)

Classes of problems:

• P = problems for which an algorithm can compute answer in polynomial time
• NP = includes problems for which no P algorithm is known

Beware: NP stands for "nondeterministic, polynomial time (on a theoretical Turing Machine)"

❖ ... Complexity Classes

Computer Science jargon for difficulty:

• tractable … have a polynomial-time algorithm (useful in practice)
• intractable … no tractable algorithm is known (feasible only for small n)
• non-computable … no algorithm can exist

Computational complexity theory deals with different degrees of intractability

❖ Generate and Test Algorithms

In scenarios where

• it is simple to test whether a given state is a solution
• it is easy to generate new states   (preferably likely solutions)

then a generate and test strategy can be used.

It is necessary that states are generated systematically

• so that we are guaranteed to find a solution, or know that none exists
  • some randomised algorithms do not require this, however
    (more on this later in this course)

❖ ... Generate and Test Algorithms

Simple example: checking whether an integer n is prime

• generate/test all possible factors of n
• if none of them pass the test  ⇒ n is prime

Generation is straightforward:

• produce a sequence of all numbers from 2 to n-1

Testing is also straightfoward:

• check whether next number divides n exactly

❖ ... Generate and Test Algorithms

Function for primality checking:

isPrime(n):
|  Input  natural number n
|  Output true if n prime, false otherwise
|
|  for all i=2..n-1 do      // generate
|  |  if n mod i = 0 then   // test
|  |     return false       // i is a divisor => n is not prime
|  |  end if
|  end for
|  return true              // no divisor => n is prime

Complexity of isPrime is O(n)

Can be optimised: check only numbers between 2 and `|__sqrt n__|`     ⇒   O(`sqrt n`)

❖ Example: Subset Sum

Problem to solve ...

Is there a subset S of these numbers with sum(S)=1000?

 34,  38,  39,  43,  55,  66,  67,  84,  85,  91,
101, 117, 128, 138, 165, 168, 169, 182, 184, 186,
234, 238, 241, 276, 279, 288, 386, 387, 388, 389

General problem:

• given n integers and a target sum k
• is there a subset that adds up to exactly k?

❖ ... Example: Subset Sum

Generate and test approach:

subsetsum(A,k):
|  Input  set A of n integers, target sum k
|  Output true if Σb∈Bb=k for some B⊆A
|         false otherwise
|
|  for each subset S⊆A do
|  |  if sum(S)=k then
|  |     return true
|  |  end if
|  end for
|  return false

• How many subsets are there of n elements?
• How could we generate them?

❖ ... Example: Subset Sum

Given: a set of n distinct integers in an array A …

• produce all subsets of these integers

A method to generate subsets:

• represent sets as n bits   (e.g. n=4, 0000, 0011, 1111 etc.)
• bit i represents the i ^th input number
• if bit i is set to 1, then A[i] is in the subset
• if bit i is set to 0, then A[i] is not in the subset
• e.g. if A[]=={1,2,3,5} then 0011 represents {1,2}

❖ ... Example: Subset Sum

Algorithm:

subsetsum1(A,k):
|  Input  set A of n integers, target sum k
|  Output true if Σb∈Bb=k for some B⊆A
|         false otherwise
|
|  for s=0..2n-1 do
|  |  if k = Σ(ith bit of s is 1) A[i] then
|  |     return true
|  |  end if
|  end for
|  return false

Obviously, subsetsum1 is O(2ⁿ)

❖ ... Example: Subset Sum

subsetsum2(A,n,k):
|  Input  array A, index n, target sum k
|  Output true if some subset of A[0..n-1] sums up to k
|         false otherwise
|
|  if k=0 then
|     return true   // empty set solves this
|  else if n=0 then
|     return false  // no elements => no sums
|  else
|     return subsetsum(A,n-1,k-A[n-1]) ∨ subsetsum(A,n-1,k)
|  end if

❖ ... Example: Subset Sum

Cost analysis:

• C_i = #calls to subsetsum2() for array of length i
• for best case, C_n = C_n-1    (why?)
• for worst case, C_n = 2·C_n-1   ⇒ C_n = 2ⁿ

Thus, subsetsum2 also is O(2ⁿ)

❖ ... Example: Subset Sum

Subset Sum is typical member of the class of NP-complete problems

• intractable … only algorithms with exponential performance are known
  • increase input size by 1, double the execution time

  • increase input size by 100, it takes 2¹⁰⁰ = 1,267,650,600,228,229,401,496,703,205,376 times as long to execute

• but if you can find a polynomial algorithm for Subset Sum,
        then any other NP-complete problem becomes P !

❖ Summary

• Big-Oh notation
• Asymptotic analysis of algorithms
• Examples of algorithms with logarithmic, linear, polynomial, exponential complexity

• Suggested reading:
  • Sedgewick, Ch.2.1-2.4,2.6