Summation and Iterative Algorithms

Bart Massey

Review of Analysis Framework

  • Classes, problems, instances: a problem has a formal description

  • An algorithm solves all instances of a given problem: an algorithm has a pseudocode description

  • Complexity measures are runtime (T[x], in "operations") and space usage (S[x], in bits) of a given instance (x)

  • Group all instances of given size in bits (typically) and talk about their statistical properties: max, average

  • Measure the asymptotic complexity: growth of the function describing the statistical complexity as instance size grows

  • Use O, Ω, Θ to approximate asymptotic complexity for convenience

  • Laws: Given f1 in O(g1) and f2 in O(g2)

    • f1 + f2 in max(O(g1), O(g2))

    • f1 × f2 in O(g1) × O(g2)

Analyzing sorting

SEQUENCE SORTING

Instance: A sequence s of elements drawn from a
total-ordered set S (with an operation ≤)

Problem: Find a sequence t drawn from S s.t.
  t ∈ perm(s) ∧ ∀ ij ∈ 1..|S| . i < j => t[i] ≤ t[j]

A dumb sorting algorithm

ALGORITHM DUMBSORT
To sort s:
  for each permutation t of s
    if t satisifies the definition of sorted
      return t

  • Hard to see even correctness: need to prove that outer loop will ever complete

  • Lemma: Some permutation of any sequence of total-ordered elements is sorted

  • Proof: By induction on length of sequence. Pick a largest element of the sequence, then find ordering of remaining elements. Base case is empty sequence, which is sorted.

Analysis of DUMBSORT

  • Let n = |s| (abstract element sizes), consider worst-case

  • for loop runs O(n!) times

  • Hard to see how long test takes. Need to expand pseudocode

ALGORITHM DUMBSORT
To sort s:
  for each permutation t of s
    for i in 1..|s|
      for j in i+1..|s|
        if s[i] > s[j]
          continue outer loop
    return t

Aside: Gauss's Sum

  • We talked last time about

      sum(1..n) = n (n + 1) / 2
    
  • Probably worth a proof. Use induction on n. Base case: true for n = 1. Inductive case:

      sum(1..n+1) = (n + 1) (n + 2) / 2
                  = (n^2 + 3n + 2) / 2
                  = (n (n + 1)) / 2 + (n + 1)
                  = sum(1..n) + (n + 1)
    
  • Corollary: sum(1..n) in O(n2)

Gauss's Sum for DUMBSORT

  • Consider innermost loops. Do compare (n - 1) + (n - 2) + ... + 1 times

  • But by previous, this is O(n2)

  • Θ(n!) = Θ(sqrt(n) (n/e)n)

  • So overall performance is in Θ(sqrt(n) n2 (n/e)n) which is in the complexity class nn by definition of that class

Another Example

UNIQUE ELEMENTS

Given: An array a

Find: An array that is a permutation of the set of elements of a

ALGORITHM SWAP-IN

To find the unique elements of a:
  i ← 1
  while i < |a|
    for j in 1..i
      if a[j] = a[i+1]
        copy the last element of a to position i + 1
        delete the last element of a
        continue outer loop
    i ← i + 1
  return a

  • Correctness:

    • Algorithm terminates, since |a| - i reduces by one at each step of the while loop

    • Algorithm is partially correct, by an inductive proof not given

  • Running time:

    • Outer loop runs O(|a|) times by termination argument

    • Therefore inner loop runs 1 + 2 + ... + a-1 times in worst case, which by Gauss's Sum is O(|a|^2)