Time efficiency - a measure of amount of time for an algorithm to execute.
Space efficiency - a measure of the amount of memory needed for an algorithm to execute.
Complexity theory - a study of algorithm performance
Function dominance - a comparison of cost functions
Asymptotic dominance - comparison of cost functions when n is large.
Function g asymptotically dominates function f if there are positive constants c and n_{0} such that
c*g(n) >= f(n) for all n>= n_{0}
That is, g asymptotically dominates f if g dominates f for all "large" values of n.
Given two nonnegative functions f and g, f = O(g) if and only if g asymptotically dominates f
"f is of the order g" or "The order of f is g"
Formally, if f(n) and g(n) are functions defined for positive integers then f(n) =
O(g(n))
if there exists a c such that |f(n)| <=c|g(n)| for all sufficiently large positive
integers n
We want to show that n^{2 }dominates the polynomial 3n^{2} + 3n + 10, or, in other words
3n^{2} + 3n + 10 = O(n^{2})
Let c = 4 (there are lots of c's to choose from) and show that there exists an n_{0} in which the equation holds
3n^{2} + 3n + 10 <=4n^{2} 0 <= n^{2}-3n-10 0 <= (n-5)(n+2)
so for n >= 5 we found c=4
Here is an example where n may have to become larger in order for g(x) to dominate.
Find an n when 2^{n} > 8n^{4}
n log_{2} 2 > log_{2}8 + 4 log_{2}n
n > 3 + 4 log_{2} n
(n-3)/4 > log_{2} n
so n > 16
Here are some simplifications that can be applied
2n^{2} - n^{2} = n^{2}
Some other rules
Let X and Y denote variables and a,b,c, and d denote constants
In order of dominance (top is most dominant)
Function | condition | common name |
N^{n} | ||
N! | N factorial | |
a^{n} | dominates b^{n} if a > b | exponential |
N^{c} | dominates N^{d} if c>d | polynomial (cubic, quadratic, etc.) |
n log n | n log n | |
n | linear | |
log n | logarithmic (regardless of base) | |
1 | constant |
> log2 := loglogplot (log[2](x), x=1..lim, color=green):
> lin := loglogplot (x, x=1..lim, color=gold):
> nlogn := loglogplot (x*log[2](x), x=1..32, color=blue):
> quad :=loglogplot (x^2, x=1..32, color=yellow):
> cube := loglogplot (x^3, x=1..lim, color=violet):
> quart := loglogplot (x^4, =1..lim, color=maroon):
> expon := loglogplot (2^x, x=1..lim, color=red):
> fact := loglogplot (factorial(x), x=1..10, color=orange):
N |
log_{2}N |
n*log_{2}N |
N^{2} |
N^{3} |
2^{N} |
3^{N} |
1 | 0 | 0 | 1 | 1 | 2 | 3 |
2 | 1 | 2 | 4 | 8 | 4 | 9 |
4 | 2 | 8 | 16 | 64 | 16 | 81 |
8 | 3 | 24 | 64 | 512 | 256 | 6561 |
16 | 4 | 64 | 256 | 4096 | 65,536 | 43,046,721 |
32 | 5 | 160 | 1024 | 322,768 | 4,294,967,296 | … |
64 | 6 | 384 | 4096 | 262,144 | (Note 1) | … |
128 | 7 | 896 | 16,384 | 2,097,152 | (Note 2) | … |
256 | 8 | 2048 | 65,536 | 1,677,216 | ???????? | … |
Note1: The value here is approximately the number of machine instructions executed by a 1 gigaflop computer in 5000 years.
Algorithm time estimating function |
Number of data collections processed on a computer 1000 times faster |
N |
1000.00 |
N*log_{2}N |
140.22 |
N^{2} |
31.62 |
N^{3} |
10.00 |
2^{N} |
9.97 |
3^{N} |
6.29 |
4^{N} |
4.98 |
Control structure or form of loop | Running Time |
assignment statement | O(1) |
expression | O(1) |
the sequence Stmt_{1 }Stmt_{2} |
Max [ O(S_{1}), O(S_{2}) ] |
if (condition) Stmt1 else Stmt2 |
Max [ O(cond), O(S_{1}), O(S_{2}) ] |
for (i=1; i<=n; i++) Stmt1 |
O(n * S_{1}) |
algorithms without looping or recursion | O(1) |
for (i=a; i<=b; i++){ //body requiring constant time } |
O(1) |
for (i=a; i<=n; i++){ //body requiring constant time } |
O(n) -- linear time |
for (i=a; i<=n; i++){ for(j=b; j<=n; j++){ //body requiring constant time } } |
O(n^{2}) -- quadratic time |
for (i=a; i<=n; i++){ //body requiring O(M) time } |
O(n * M) |
//---------------------------------------------------------------------- // pythag.cpp // This program prints all Pythagorean triples up through some user- // specified value. All output triples are in increasing order. //---------------------------------------------------------------------- #include <iostream.h> int main() { int maxLen; int small; int next; int last; cout << "Max. side length: "; cin >> maxLen; small = 1; while (small <= maxLen) { // INV (prior to test): All triples in the range // (1..small-1, 1..maxLen, 1..maxLen) have been output && small<=maxLen+1 next = small; while (next <= maxLen) { // INV (prior to test): All triples in the range // (small, 1..next-1, 1..maxLen) have been output && next<=maxLen+1 last = next; while (last <= maxLen) { // INV (prior to test): All triples in the range // (small, next, 1..last-1) have been output && last<=maxLen+1 if (last*last == small*small + next*next) cout << small << ", " << next << ", " << last << '\n'; last++; } next++; } small++; } return 0; }
n = maxLen;
O(1) O(n) O(n^{2}) O(n^{3})