Analyzing Algorithms

Prediction of resource use:

• time
• chip space
• memory
• communication resources

Model of Computation  (implementation technology)

Random Access Machine

1. memory accesses are all the same cost
2. One instruction executed at a time

Terms

• Input Size -- Problem dependent, in sorting -- number of items, in multiplication -- number of bits.
• C_i = the cost of executing a line i
• times -- number of times a line is executed

Insertion-Sort(A)	Cost	Times
1 for j ¬ 2 to length[A]	C1	n
2   do key ¬ A[j]	C2	n -1
3      Insert A[j] into the sorted sequence A[1..j-1].	0	n - 1
4      i ¬ j - 1	C4	n - 1
5      while i > 0 and A[i] > key	C5	n å j = 2  tj
6        do A[i + 1] ¬ A[i]	C6	n å j = 2  (tj - 1)
7           i ¬ i - 1	C7	n å j = 2  (tj - 1)
8      A[i + 1] ¬ key	C8	n - 1

t_j = the number of times line 5 is executed, or how long you search for your spot

Best case ( t_j = 1) no search required, list is already sorted.

T (n) = ( C₁ + C₂ + C₄ + C₅ + C₈ )n - ( C₂ + C₄ + C₅ + C₈ )

         =                  a                        n   +               b

T (n)  is a linear function of n

Worst case analysis:

Input is "all wrong":   a₁ ³   a₂  ³ a₃ ³ ...  a_n means that   t_j = j  ( we must compare all the elemnts each time!)

T (n) = ( C₅ / 2 + C₆ / 2 + C₇ / 2 ) n ² + n( C₁ + C₂ + C₄ + C₅ / 2 - C₆ / 2 - C₇ / 2 + C₈  ) - ( C₂ + C₄ + C₅ + C₈ )

         = a n² + b n + c  -- a quadratic function of n

Why use a worst case analysis

1. Upper bound for all cases
2. Worst case "may" be a typical case
3. Average case may be approximately the worst case (( t_j = j / 2 ) is roughly quadratic.)
4.  Often it is hard to pick average cases and compute expected times.

Rate of Growth of Functions

 a n² + b n + c  or  O (n² ) is an order of growth.