Analysis of an Algorithm
Document last modified: 

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.
Find_Largest (A)
//@ pre A != null;
//@ post (\forall int i; 1 <= i && i <= A.length; A[\result] >= A[i]);
//    post: result = index in A of the largest element in A 

 

 Cost

Times Executed
1    location ← 1 c1 
2    for i ←2 to length[A] do c2 
3       if A[location] < A[i] then c3 
4          location ← i c4 
5    return location c5