Week 02b: Analysis of Algorithms


Analysis of Algorithms


Running Time2/63

An algorithm is a step-by-step procedure

Most algorithms map input to output

[Diagram:Pic/runningTime-small.png]


Empirical Analysis3/63

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

[Diagram:Pic/experimental-small.png]


... Empirical Analysis4/63

Limitations:


Theoretical Analysis5/63


Pseudocode6/63


... Pseudocode7/63

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


... Pseudocode8/63

Control flow

Function declaration Expressions


Exercise #1: Pseudocode9/63

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 #2: Pseudocode11/63

Implement the following pseudocode instructions in C

  1. A is an array of ints

    ...
    swap A[i] and A[j]
    ...
    

  2. head points to beginning of linked list

    ...
    swap head and head->next
    ...
    

  3. S is a stack

    ...
    swap the top two elements on S
    ...
    


  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 Model13/63

RAM = Random Access Machine


Primitive Operations14/63

Examples:


Counting Primitive Operations15/63

By inspecting the pseudocode …

Example:

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 Times16/63

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

Define: 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 Times17/63

Seven commonly encountered functions for algorithm analysis


... Estimating Running Times18/63

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

[Diagram:Pic/growthFunctions-small.jpg]


... Estimating Running Times19/63

The growth rate is not affected by constant factors or lower-order terms

[Diagram:Pic/constant-small.png]


... Estimating Running Times20/63

Changing the hardware/software environment

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


Exercise #3: Estimating running times21/63

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 #4: Estimating running times22/63

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


Big-Oh Notation24/63

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

f(n) is O(g(n))

if there are positive constants c and n0 such that

f(n) ≤ c·g(n)    ∀nn0


... Big-Oh Notation25/63

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
  

[Diagram:Pic/bigOh-small.png]


... Big-Oh Notation26/63

[Diagram:Pic/bigOh-2-small.png]

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


Exercise #5: Big-Oh27/63

Show that

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


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


Big-Oh and Rate of Growth29/63

f(n) is O(g(n))g(n) is O(f(n))
g(n) grows fasteryesno
f(n) grows fasternoyes
same order of growthyesyes


Big-Oh Rules30/63


Exercise #6: Big-Oh31/63

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



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

which is O(n2)


Asymptotic Analysis of Algorithms33/63

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

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


Example: Computing Prefix Averages34/63


... Example: Computing Prefix Averages35/63

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)

2·O(n2) + 3·O(n) + O(1) = O(n2)

Time complexity of algorithm prefixAverages1 is O(n2)


... Example: Computing Prefix Averages36/63

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 Search37/63

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 Search38/63

Successful search for a value of 8:

[Diagram:Pic/binary-search-found-small.png]


... Example: Binary Search39/63

Unsuccessful search for a value of 7:

[Diagram:Pic/binary-search-failed-small.png]


... Example: Binary Search40/63

Cost analysis:

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


... Example: Binary Search41/63

Why logarithmic complexity is good:

[Diagram:Pic/log-complexity-small.png]


Math Needed for Complexity Analysis42/63


Exercise #7: Analysis of Algorithms43/63

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 #8: Analysis of Algorithms45/63

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-Oh47/63

big-Omega

big-Theta


... Relatives of Big-Oh48/63


... Relatives of Big-Oh49/63

Examples:


Complexity Classes50/63

Problems in Computer Science …

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


... Complexity Classes51/63

Computer Science jargon for difficulty:

Computational complexity theory deals with different degrees of intractability


Generate and Test Algorithms


Generate and Test53/63

In scenarios where

then a generate and test strategy can be used.

It is necessary that states are generated systematically


... Generate and Test54/63

Simple example: checking whether an integer n is prime

Generation is straightforward: Testing is also straightfoward:


... Generate and Test55/63

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 Sum56/63

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:


... Example: Subset Sum57/63

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


... Example: Subset Sum58/63

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

A method to generate subsets:


... Example: Subset Sum59/63

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(2n)


... Example: Subset Sum60/63

Alternative approach …

subsetsum2(A,n,k)
(returns true if any subset of A[0..n-1] sums to k; returns false otherwise)

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 Sum61/63

Cost analysis:

Thus, subsetsum2 also is O(2n)


... Example: Subset Sum62/63

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


Summary63/63



Produced: 2 Dec 2018