CSC300 / CSC402: Example: Computing Max [9/9] Previous pageContents

From Week 1: Efficient way to compute max

Loop Invariant: m contains the maximum value we've seen from a[0] through a[i-1].

01
02
03
04
05
06
07
08
09
10
11
 
package algs11;
import stdlib.*;
public class PlaygroundMaxPerformance {
  public static double max (double[] a) {
    double m = a[0];
    for (int i = 1; i < a.length; i++) {
      if (m < a[i]) { m = a[i]; }
    }
    return m;
  }
}

We say this code is efficient. Time complexity: O(n).

From Week 1: Inefficient way to compute max:

Loop Invariant (outer loop): The elements from a[0] through a[i-1] are not the max.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
 
package algs11;
import stdlib.*;
public class PlaygroundMaxPerformance {
  public static double max (double[] a) {
    for (int i=0; i < a.length; i++) {
      boolean isMax = true;
      for (int j=0; j<a.length; j++)
        if (a[j] > a[i])
          isMax = false;
      if (isMax) return a[i];
    }
    throw new IllegalArgumentException(); 
  }
}

We say this code is inefficient. Time complexity: O(n^2).

Previous pageContents