Big-O - top of Musings page

The most important thing about big-O for us is that it is a QUICK estimate of algorithm performance.

The main categories of big-O functions are:

1/n < 1 < log log n < log n < n^(1/2) < n < n log n < n^(3/2) < n^2 < n^3 < 2^n < n! < n^n

• < 1 means the function is decreasing
• < n growing slowly
• >= n^2 very rapid growth
• >= 2^n astronomical growth
• > n! stupendous growth
• > n^n WOW!
  

Relatives of big-O are icing on the cake in this class.

A little bit more precisely, with a, b and c real numbers and 0 < a < b:

$\frac{1}{N} < 1 < log log N < log N < {N}^{a} < {N}^{a}log N < {N}^{b}< {c}^{N} < N! < {N}^{N}$

Big-O Practice 1 - top of Musings page

1. for (i = 0; i < N; i++)
   
   
2. for (i = 0; i < N; i = i + 2)
   
   
3. for (i = 1; i < N; i = 2 * i)
   
   
4. for (i = 0; i < N; i++)
     for (j = 0; j < N; j++)
   
   
5. for (i = 0; i < N; i = i + 2)
     for (j = 0; j < N; j = j + 2)
   
   
6. for (i = N; i > 0; i = i/2)
     for (j = 0; j < N; j++)
   
   
7. for (i = N; i > 0; i = i/2)
     for (j = N; j > 0; j = j/2)
   
   
8. for (i = N; i > 0; i = i/2)
     for (j = i; j > 0; j = j/2)
   
   
9. for (i = 0; i < N; i++)
     for (j = 0; j < N; j++)
       for (k = 0; k < N; k++)
   
   
10. for (i = 0; i < N; i++)
      for (j = N; j > 0; j = j / 2)
        for (k = 0; k < N; k++)
    
    
11. for (i = 0; i < N; i++)
      for (j = 0; j < N; j++)
        for (k = N; k > 0; k /= 2)
    

Big-O Practice 2 - top of Musings page

1. What is the big-O performance estimate of the following function?
   int f (int n) {
     int sum = 0;
     for (i = 0; i < n; i++)
       sum += i;
     return sum;
   } // end f
   
   
2. What is the big-O performance estimate of the following function?
   int f (int n) {
     int sum = 0;
     for (i = 0; i < n; i = i + 10)
       sum += i;
     return sum;
   } // end f
   
   
3. What is the big-O performance estimate of the following function?
   int f (int n) {
     int sum = 0;
     for (i = 0; i < n*n; i++)
       sum += i;
     return sum;
   } // end f
   
   
4. What is the big-O performance estimate of the following function?
   int f (int n) {
     int sum = 0;
     for (i = 0; i < n * Math.log(int n); i++)
       sum += i;
     return sum;
   } // end f
   
   
5. What is the big-O performance estimate of the following function?
   int f (int n) {
     int sum = 0;
     for (i = 0; i < n*n*n; i++)
       sum += i;
     return sum;
   } // end f
   
   
6. What is the big-O performance estimate of the following function?
   int f (int n) {
     int sum = 0;
     for (i = 1; i < n; i = 2 * i) // start at 1
       sum += i;
     return sum;
   } // end f
   
   
7. What is the big-O performance estimate of the following function?
   int f (int n) {
     int sum = 0;
     for (i = 2; i < n; i = i * i) // start at 2
       sum += i;
     return sum;
   } // end f
   
   
8. What is the big-O performance estimate of the following function?
   int f (int n) {
     int sum = 0;
     for (i = n; i > 0; i--)
       sum += i;
     return sum;
   } // end f
   
   
9. What is the big-O performance estimate of the following function?
   int f (int n) {
     int sum = 0;
     for (i = n; i > 0; i = i / 2) // typo
       sum += i;
     return sum;
   } // end f
   
   
10. What is the big-O performance estimate of the following function?
    int f (int n) {
      int sum = 0;
      for (i = n; i > 0; i = i / 5)
        sum += i;
      return sum;
    } // end f
    
    
11. What is the big-O performance estimate of the following function?
    int f (int n) {
      int sum = 0;
      for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
          sum += i + j;
      return sum;
    } // end f
    
    
12. What is the big-O performance estimate of the following function?
    int f (n) {
      if (n <= 0) return 1;
      return n + f(n-1);
    } // end f
    
    
13. What is the big-O performance estimate of the following function?
    int f (int n) {
      if (int n <= 1) return 1;
      return f(n-1) + f(n-2);
    } // end f
14. What is the big-O performance estimate of the following function?
    int f (int n) {
      if (n <= 1) return 1;
      return n + f(n/2);
    } // end f
    
    
15. What is the big-O performance estimate of the following function?
    int f (int n) {
      if (n < 10) return n;
      return n%10 + f(n/10);
    } // end f
    
    
16. What is the big-O performance estimate of the following function?
    int f (int n, int b) {
      if (n < b) return n;
      return n%b + f(n/b, b);
    } // end f
    
    
17. What is the big-O performance estimate of the following function?
    // Assume a and b are conformable matrices:
    // columns of a = rows b
    int [][] f (int [][] a, int [][] b) {
      int [] [] c = new int [a.[0].length][b.length]
      for (int i = 0; i < c.length; i++)
        for (int j = 0; j < c[0].length; j++) {
          int sum = 0
          for (int k = 0; k < b.length; k ++ )
            sum += a[i][k] * b [k][j]
          c[i][j] = sum;
        } // end for each j
      return c;
    } // end f
    
    
18. What is the big-O performance estimate of the following function?
    // Assume a and b are conformable matrices:
    // dimensions of a = dimensions of b
    int [][] f (int [][] a, int [][] b) {
      int [] [] c = new int [a.length][a[0].length]
      for (int i = 0; i < c.length; i++)
        for (int j = 0; j < c[0].length; j++)
          c[i][j] = a[i][j] + b[i][j];
      return c;
    } // end f
    
    
19. ?