permutation - rearrangement of items

$ == “such that”

Insertion sort

Example: Array = SORTED J UNSORTED

j = item in array

8 2 4 9 3 6

2 8 4 9 3 6

2 4 8 9 3 6

2 4 8 9 3 6

2 3 4 8 9 6

Running Time

• depends on input order (e.g. already sorted, reverse order)
• depends on input size
• parameters in input size
• want upper bounds

Kinds of analysis

Worst case

T(n) = max time on any input of size n

Average case

T(n) = expected time of all inputs of size n

(Need an assumption of statistical distribution of inputs)

Best case

Bogus

What is insertion sort’s worst case time?

Depends on computer

• relative speed (on same machine)
• absolute speed (on different machine)

Big Idea of Algorithms

Asymptotic analysis

1. ignore machine dependent constants
2. look at growth of T(n) as n → ∞ (the running time)

Asymptotic Notation

(Theta notation)

Θ notation

• drop low order terms
• ignore leading constants

Example: 3n^{3<_sup> + 90n2<_sup> - 5n + 6046 = Θ(n3)}

as n → ∞, Θ(n^{2<_sup>) algorithm always beats an Θ(n3<_sup>) algorithm}