Big-O - top of Musings page

by Nick Duchon

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

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:

1N<1<loglogN<logN<Na<NalogN<Nb<cN<N!<NN\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

Here are some examples of loops. Your assignment, should you choose to accept is, is to give big-O estimates for each loop.
  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

Here are some problems to help you practice your understanding of Big-O, and related estimates.
Version 2.0 - updated on Aug 20, 2015.

  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. ?