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:
Here are some examples of loops. Your assignment, should you choose
to accept is, is to give big-O estimates for each loop.
- for (i = 0; i < N; i++)
- for (i = 0; i < N; i = i + 2)
- for (i = 1; i < N; i = 2 * i)
- for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
- for (i = 0; i < N; i = i + 2)
for (j = 0; j < N; j = j + 2)
- for (i = N; i > 0; i = i/2)
for (j = 0; j < N; j++)
- for (i = N; i > 0; i = i/2)
for (j = N; j > 0; j = j/2)
- for (i = N; i > 0; i = i/2)
for (j = i; j > 0; j = j/2)
- for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
for (k = 0; k < N; k++)
- for (i = 0; i < N; i++)
for (j = N; j > 0; j = j / 2)
for (k = 0; k < N; k++)
- for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
for (k = N; k > 0; k /= 2)
Here are some problems to help you practice your understanding of
Big-O, and related estimates.
Version 2.0 - updated on Aug 20, 2015.
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- ?