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

• < 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\left\{1\right\}\left\{N\right\} < 1 < log log N < log N < \left\{N\right\}^\left\{a\right\} < \left\{N\right\}^\left\{a\right\}log N < \left\{N\right\}^\left\{b\right\}< \left\{c\right\}^\left\{N\right\} < N! < \left\{N\right\}^\left\{N\right\}$

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