# 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)