Analysis of an Algorithm

Assignment

1. Write down for each statement the number of times the statement is executed in the worst case.
2. Compute T(n), i.e., the running time of Find_Largest, and simplify (if possible) by combining terms.
3. What data produces the worst case? The best case?
4. Is the worst case actually any worst than the best case? Think Big-O.
5. Write down the for loop's loop invariant.

2. Compute T(n), i.e., the running time of Find_Largest, and simplify (if possible) by combining terms.

   T(n) = c₁ + c₂n + c₃(n - 1) + c₄(n - 1) + c₅ 

          = c₁ + n(c₂+c₃+c₄) - (c₃+c₄) + c₅ 
   
          = n(c₂+c₃+c₄) + c₁ + c₅ - (c₃+c₄)
   
          = an + b                 for some constants a and b.
   
    

3. What data produces the worst case? Data that executes line 4 each iteration, when sorted in ascending order.
    

   The best case? Data that never executes line 4, when sorted in descending order.
    

4. Is the worst case actually any worst than the best case? Think Big-O.

   No. O(n) = T(n) = an + b
    

5. Write down the for loop's loop invariant.

   The loop invariant is:

       /*@ loop_invariant (\forall int j;

                                        1<=j && j < i && 1 <= location && location < i;

                                        A[j] <= A[location]);                                                     @*/
    

   • Invariant Property:  ∀j: 1 ≤ j < i, 1 ≤ location < i,  A[j] ≤ A[location]
      
   • Invariant Property Correctness:
     1. Initialization: Prior to the loop test of (i ≤ length[A]) we know: i = 2 and location = 1, therefore the invariant property is: ∀j: 1 ≤ j < 2, A[1] ≤ A[1], which is obviously true
     2. Maintenance: At the end of each pass of the loop: 
        • at the beginning of the loop body the invariant property held, which means that 'location' held the index to the largest value in A[1..(i - 1)]
        • during the execution of the loop body, A[location] was compared to A[i] and if A[i] was found to be greater than A[location], then 'location' was updated to have the index stored in 'i'.
        • therefore at the end of the loop, (after 'i' has been incremented by 1), the invariant property must continue to hold.
     3. Termination: At loop termination we know these things:
        1. the invariant property ∀j: 1 ≤ j < i, 1 ≤ location < i, A[j] ≤ A[location] holds
        2. the semantics of the for-loop are that i = length[A] + 1
        3. therefore  ∀j: 1 ≤ j < (length[A] + 1), 1 ≤ location < (length[A] + 1), A[j] ≤ A[location] holds

           which says that for any value of j between 1 and length[A] (inclusive), that A[location] is greater than or equal to A[j], and so 'location' holds the index to a value in A that is at least as large as any other value in A.

           Find_Largest (A)
           1	location ← 1
           2	-- "j: 1 ≤ j < i, 1 ≤ location < i,  A[j] ≤ A[location]    for i ← 2 to length[A] do
           3	if A[location] < A[i] then
           4	location ← i
           5	return location