March:11(Wed)

CS 163-01 Lab #11

Again consider those six program fragments:

    sum = 0;
    for ( i = 0; i < n; i++ )
        for ( j = 0; j < 100; j++ )
            sum++;

    sum = 0;
    for ( i = 0; i < n; i++ )
        for ( j = 0; j < n; j++ )
            sum++;

    sum = 0;
    for ( i = 0; i < n; i++ )
        for ( j = 0; j < n * n; j++ )
            sum++;

    sum = 0;
    for ( i = 0; i < n; i++ )
        for ( j = 0; j < i; j++ )
            sum++;

    sum = 0;
    for ( i = 0; i < n; i++ )
        for ( j = 0; j < i * i; j++ )
            for ( k = 0; k < j; k++ )
                sum++;

    sum = 0;
    for ( i = 1; i < n; i++ )
        for ( j = 1; j < i * i; j++ )
            if ( j % i == 0 )
                for ( k = 0; k < j; k++ )
                    sum++;

Use your data from timing those program fragments for the previous lab exercise to determine each program fragment's time function "O(n)" or "O(n²)" or "O(n³)" or "O(n⁴)" or ....

If the time goes *2 when data goes *2, time function is O(n), linear
or if the time goes *2² when data goes *2, time function is O(n²), quadratic
or if the time goes *2³ when data goes *2, time function is O(n³), cubic
or ....
E.g. if you see the following:

    n   time
 10000  1.2s.
  *2     *4
 20000  4.8s.
  *2     *4ish
 40000  19s.
  *2     *4 approx.
 80000  95s.

then with that data, the time function is O(n²). When doing this, focus on times greater than 0.5s. because times smaller than that are actually inaccurate measures of code's operations (some fractions of a second are spent actually loading the program into memory, initializing the Java Virtual Machine, etc. — overhead).

If execution takes too long, e.g. if your times appear like the following:

    n   time
 10000  1.2s.
  *2
 20000  70s.
  *2
 40000  ............

then instead of using the factor 2 as specified above, use the factor 1.5 instead.
Then if the time goes *1.5 when data goes *1.5, time function is O(n), linear
or if the time goes *1.5² when data goes *1.5, time function is O(n²), quadratic
or if the time goes *1.5³ when data goes *1.5, time function is O(n³), cubic
or if the time goes *1.5⁴ when data goes *1.5, time function is O(n⁴), quartic
or ....
E.g. if you see the following:

    n   time
  1000  1.2s.
  *1.5   *1.5³
  1500  4.05s.
  *1.5   *1.5³ approximately
  2250  13s.
  *1.5   *1.5³ approximately
  3375  43s.

then with that data, the time function is O(n³).