Analysis of Non-Recursive Insertion Sort

Insertion Sort

The number of instructions executed by a polynomial time operation is dependent on the size of the problem on which the operation is working.   The Insertion-Sort is an example of a polynomial time operation. Worst case: O(n2)

Example

loop invariant    At start of each iteration of Line 1: A[1..j-1]  is sorted

Figures a-e: immediately after assignment to j (i.e. darkened) j=2, A[1..1] is sorted j=3, A[1..2] is sorted j=4, A[1..3] is sorted j=5, A[1..4] is sorted j=6, A[1..5] is sorted A[1..6] is sorted

Analysis

• T(n) = a function dependent on n (input size) that describes the number of instructions executed

  In general, count number of times each instruction is executed:

  T(n) = c₁n + c₂(n-1) + c₄(n-1) + c₅ + c₆ + c₇ + c₈(n-1)

t_j = # of times the while loop test is executed for value j.

• Best case - Array A is sorted, lines c₆ and c₇ not executed.

  1	2	3	4	5	6
  1	2	3	4	5	6

  Line c2	key ← A[j]	value from the unsorted array (loop invariant ensures A[1..j-1] is sorted)
  Line c5	A[i] ≤ key	while  loop test executed n-1 times but only iterated when key should be inserted into sorted array A[1..j-1] tj=1 because for each j the while loop test executed 1 time.
  Line c6 and c7		Not executed.
  T(n) = c1n + c2(n-1) + c4(n-1) + c5(n-1) + c8(n-1)        = (c1+ c2 + c4 + c5 + c8)n - (c2 + c4 + c5 + c8)        = an + b for some a and b constants

  Question 2.20 What is the order of the best case for T(n) = an + b?
                           That is: T(n) is Ω( ? ).

   

• Worst case - Array A is reverse sorted, lines c₆ and c₇ executed maximum number of times.
   

  1	2	3	4	5	6
  6	5	4	3	2	1

  Line  c2	key ← A[j]	value from the unsorted array (loop invariant ensures A[1..j-1] is sorted)
  Line  c5	A[i]>key	while condition tested n-1 times and iterated when key should be inserted into sorted array A[1..j-1] tj=j for j=2,3, ..., n. tj=j because for each j the while loop test executed j times due to reverse sorted data.

  Closed-end formula tj=j for j=2,3, ..., n We proved this earlier using mathematical induction. since: = n(n+1)/2 - n = (n2 + n - 2n)/2 = (n2 - n)/2 = n(n-1)/2

  Question 2.21

  1. Can we now express T(n) as an² + bn + c, a closed-end expression, for constants a, b and c?
      
  2. What is the (highest) order of T(n) = an² + bn + c for worst case?         
                       
  3. T(n) is O( ? ).

Worst and Average case - We usually concentrate on finding the worst-case running time: the longest running time for any input of size n.

• Reasons:
  • The worst-case running time gives a guaranteed upper bound on the running time for any input.
  • For some algorithms, the worst case occurs often. For example, when searching, the worst case often occurs when the item being searched for is not present, and searches for absent items may be frequent.
  • Why not analyze the average case? Because it’s often about as bad as the worst case.

  Example: Suppose that we randomly choose n numbers as the input to insertion sort.

  • On average, the key in A[ j ] is less than half the elements in A[1..j − 1] and it’s greater than the other half.
  • On average, the while loop has to look halfway through the sorted subarray A[1..j − 1] to decide where to drop key.

    t_j = j/2.

  • Although the average-case running time is approximately half of the worst-case running time, it’s still a quadratic function of n.
     

Order of growth

Another abstraction to ease analysis and focus on the important features. Look only at the leading term of the formula for running time.

• Drop lower-order terms.
• Ignore the constant coefficient in the leading term.

Example

For insertion sort, we already abstracted away the actual statement costs to conclude that the worst-case running time is: an² + bn + c.

• Drop lower-order terms bn + c yielding: an².
   
• Ignore constant a coefficient: n².
   
• But we cannot say that the worst-case running time T(n) = n²
   
• It grows like n². But it doesn’t equal n².
   
• We say that the running time is O(n²) to capture the notion that the worst-case order of growth is n².
   
• The figure at right illustrates that x²+1000x grows as x². That is, the key term is x² and one can ignore 1000x without loss of understanding the scale of growth.
   
• We usually consider one algorithm to be more efficient than another if its worst-case running time has a smaller order of growth (e.g. x² compared to x).

Question 2.22 Which does the graph indicate is more efficient? x*x or x*x+1000x?