CSC300: Understanding Nested Loops

Contents [0/13]

Starter code [1/13]
What's the result? [2/13]
What's the result? [3/13]
What's the result? [4/13]
What's the result? [5/13]
What's the result? [6/13]
What's the result? [7/13]
What's the result? [8/13]
What's the result? [9/13]
What's the result? [10/13]
What's the result? [11/13]
What's the result? [12/13]
What's the result? [13/13]

(Click here for one slide per page)


Starter code [1/13]

file:XCountingLoops.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
package algs14;
import stdlib.*;
public class XCountingLoops {
  // To Print: StdOut.printf ("N=%3d i=%3d N-i=%d\n", N, i, N-i);
  //
  // Test variant with one, two or three nested loops
  //
  // Outermost:
  // for (long i = 1; i <= N; i = i+1) {
  // for (long i = 1; i <= N; i = i*2) {
  //
  // Next:
  // for (long j = 1; j <= N; j = j+1) {
  // for (long j = 1; j <= i; j = j+1) {
  // for (long j = 1; j <= N; j = j*2) {
  // for (long j = 1; j <= i; j = j*2) {
  //
  // Next:
  // for (long k = 1; k <= N; k = k+1) {
  // for (long k = 1; k <= j; k = k+1) {
  // for (long k = 1; k <= N; k = k*2) {
  // for (long k = 1; k <= j; k = k*2) {

  // f counts the number of times the innermost loop executes 
  static long f (long N) {
    long result = 0;
    for (long i = 1; i <= N; i = i+1) {
      for (long j = 1; j <= N; j = j+1) {
        result = result+1;
        if (N <= 64) StdOut.format ("%02d ", i);
      }
      if (N <= 64) StdOut.println ();
    }
    return result;
  }
  public static void main (String[] args) {
    f(16);

    long MIN = 256L; // for powers of ten, start with 500L
    long MAX = 3_200_000_000L;
    Stopwatch sw = new Stopwatch ();
    double prevCount = f(MIN);
    double prevTime = sw.elapsedTime ();
    for (long N = MIN*2; N <= MAX; N=N*2) {
      sw = new Stopwatch ();
      long count = f(N);
      double time = sw.elapsedTime ();
      StdOut.format ("Elapsed count f(%,13d): %,16d: %10.3f [%10.3f : %10.3f]\n", N, count, count / prevCount, time, time/prevTime);
      //StdOut.format ("Elapsed count f(%,13d): %,16d: %10.3f\n", N, count, count / prevCount);
      prevCount = count;
      prevTime = time;
    }
  }
}

What's the result? [2/13]

01
02
03
 
    for (long i = N; i > 0; i = i-1) {
      result = result+1;
    }

Choices:

  1. independent of N -- constant
  2. ~ lg N -- logarithmic
  3. ~ (lg N)^2 -- log squared
  4. ~ N -- linear
  5. ~ 2N -- linear
  6. ~ N(lg N) -- linearithmic
  7. ~ (N^2)/2 -- quadratic
  8. ~ N^2 -- quadratic
  9. ~ N^3 -- cubic
  10. ~ 2^N -- exponential

What's the result? [3/13]

01
02
03
04
05
06
 
    for (long i = N; i > 0; i = i-1) {
      result = result+1;
    }
    for (long j = N; j > 0; j = j-1) {
      result = result+1;
    }

Choices:

  1. independent of N -- constant
  2. ~ lg N -- logarithmic
  3. ~ (lg N)^2 -- log squared
  4. ~ N -- linear
  5. ~ 2N -- linear
  6. ~ N(lg N) -- linearithmic
  7. ~ (N^2)/2 -- quadratic
  8. ~ N^2 -- quadratic
  9. ~ N^3 -- cubic
  10. ~ 2^N -- exponential

What's the result? [4/13]

01
02
03
04
05
 
    for (long i = N; i > 0; i = i-1) {
      for (long j = N; j > 0; j = j-1) {
        result = result+1;
      }
    }

Choices:

  1. independent of N -- constant
  2. ~ lg N -- logarithmic
  3. ~ (lg N)^2 -- log squared
  4. ~ N -- linear
  5. ~ 2N -- linear
  6. ~ N(lg N) -- linearithmic
  7. ~ (N^2)/2 -- quadratic
  8. ~ N^2 -- quadratic
  9. ~ N^3 -- cubic
  10. ~ 2^N -- exponential

What's the result? [5/13]

01
02
03
04
05
 
    for (long i = N; i > 0; i = i-1) {
      for (long j = i; j > 0; j = j-1) {
        result = result+1;
      }
    }

Choices:

  1. independent of N -- constant
  2. ~ lg N -- logarithmic
  3. ~ (lg N)^2 -- log squared
  4. ~ N -- linear
  5. ~ 2N -- linear
  6. ~ N(lg N) -- linearithmic
  7. ~ (N^2)/2 -- quadratic
  8. ~ N^2 -- quadratic
  9. ~ N^3 -- cubic
  10. ~ 2^N -- exponential

What's the result? [6/13]

01
02
03
04
05
 
    for (long i = N; i > 0; i = i-1) {
      for (long j = N; j > i; j = j-1) {
        result = result+1;
      }
    }

Choices:

  1. independent of N -- constant
  2. ~ lg N -- logarithmic
  3. ~ (lg N)^2 -- log squared
  4. ~ N -- linear
  5. ~ 2N -- linear
  6. ~ N(lg N) -- linearithmic
  7. ~ (N^2)/2 -- quadratic
  8. ~ N^2 -- quadratic
  9. ~ N^3 -- cubic
  10. ~ 2^N -- exponential

What's the result? [7/13]

01
02
03
04
05
 
    for (long i = N; i > 0; i = i/2) {
      for (long j = N; j > 0; j = j-1) {
        result = result+1;
      }
    }

Choices:

  1. independent of N -- constant
  2. ~ lg N -- logarithmic
  3. ~ (lg N)^2 -- log squared
  4. ~ N -- linear
  5. ~ 2N -- linear
  6. ~ N(lg N) -- linearithmic
  7. ~ (N^2)/2 -- quadratic
  8. ~ N^2 -- quadratic
  9. ~ N^3 -- cubic
  10. ~ 2^N -- exponential

What's the result? [8/13]

01
02
03
04
05
 
    for (long i = N; i > 0; i = i/2) {
      for (long j = i; j > 0; j = j-1) {
        result = result+1;
      }
    }

Choices:

  1. independent of N -- constant
  2. ~ lg N -- logarithmic
  3. ~ (lg N)^2 -- log squared
  4. ~ N -- linear
  5. ~ 2N -- linear
  6. ~ N(lg N) -- linearithmic
  7. ~ (N^2)/2 -- quadratic
  8. ~ N^2 -- quadratic
  9. ~ N^3 -- cubic
  10. ~ 2^N -- exponential

What's the result? [9/13]

01
02
03
04
05
 
    for (long i = N; i > 0; i = i/2) {
      for (long j = N; j > i; j = j-1) {
        result = result+1;
      }
    }

Choices:

  1. independent of N -- constant
  2. ~ lg N -- logarithmic
  3. ~ (lg N)^2 -- log squared
  4. ~ N -- linear
  5. ~ 2N -- linear
  6. ~ N(lg N) -- linearithmic
  7. ~ (N^2)/2 -- quadratic
  8. ~ N^2 -- quadratic
  9. ~ N^3 -- cubic
  10. ~ 2^N -- exponential

What's the result? [10/13]

01
02
03
04
05
 
    for (long i = N; i > 0; i = i/2) {
      for (long j = N; j > 0; j = j/2) {
        result = result+1;
      }
    }

Choices:

  1. independent of N -- constant
  2. ~ lg N -- logarithmic
  3. ~ (lg N)^2 -- log squared
  4. ~ N -- linear
  5. ~ 2N -- linear
  6. ~ N(lg N) -- linearithmic
  7. ~ (N^2)/2 -- quadratic
  8. ~ N^2 -- quadratic
  9. ~ N^3 -- cubic
  10. ~ 2^N -- exponential

What's the result? [11/13]

01
02
03
04
05
 
    for (long i = 4; i > 0; i = i-1) {
      for (long j = 0; j < 4; j = j+1) {
        result = result+1;
      }
    }

Choices:

  1. constant
  2. logarithmic
  3. log squared
  4. linear
  5. linearithmic
  6. quadratic
  7. cubic
  8. exponential

What's the result? [12/13]

01
02
03
04
05
 
    for (long i = N; i > 0; i = i-1) {
      for (long j = 0; j < 4; j = j+1) {
        result = result+1;
      }
    }

Choices:

  1. constant
  2. logarithmic
  3. log squared
  4. linear
  5. linearithmic
  6. quadratic
  7. cubic
  8. exponential

What's the result? [13/13]

01
02
03
04
05
06
07
 
    for (long i = N; i > 0; i = i-1) {
      for (long j = 0; j < N; j = j+1) {
        for (long k = 0; k < N; k = k+1) {
          result = result+1;
        }
      }
    }

Choices:

  1. independent of N -- constant
  2. ~ lg N -- logarithmic
  3. ~ (lg N)^2 -- log squared
  4. ~ N -- linear
  5. ~ 2N -- linear
  6. ~ N(lg N) -- linearithmic
  7. ~ (N^2)/2 -- quadratic
  8. ~ N^2 -- quadratic
  9. ~ N^3 -- cubic
  10. ~ 2^N -- exponential

Revised: 2008/03/17 13:01