Algorithm Efficiency

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₀ such that

c*g(n) >= f(n) for all n>= n₀

That is, g asymptotically dominates f if g dominates f for all "large" values of n.

Big-O Notation

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  

Example

We want to show that n² dominates the polynomial  3n² + 3n + 10, or, in other words

3n² + 3n + 10 = O(n²)

Let c = 4 (there are lots of c's to choose from) and show that there exists an n₀ in which the equation holds

3n² + 3n + 10 <=4n² 0 <= n²-3n-10 0 <= (n-5)(n+2)

so for n >= 5 we found c=4

Example

Here is an example where n may have to become  larger in order for g(x) to dominate.

Find an n when 2ⁿ > 8n⁴
n log₂ 2 > log₂8 + 4 log₂n
n > 3 + 4 log₂ n
(n-3)/4 > log₂ n

so n > 16

Big-O Arithmetic

Here are some simplifications that can be applied

1. O(k*f) = O(f) That is, constants can be ignored.
2. O(f*g) = O(f) * O(g) if a function is a product then its order is the product of the orders of the factors.
3. O(f/g) = O(f) / O(g)  same for a function that is a quotient
4. O(f) > O(g) if and only if f dominates g
5. O(f+g) = Max[ O(f), O(g) ] That is, terms of lower degree can be ignored.
6. Be careful with functions that have subtraction:
   If f(n) = O(h(n)) and g(n) = O(h(n)) then
   f(n)-g(n) is not equal to O(h(n)) - O(h(n)) = 0

2n² - n² = n²

Some other rules

7. The powers of n are ordered according to the exponent n^a = O(n^b) iff a <= b
8. The order of log n is independent of the base taken log_a n = O(log_b n) for all a, b > 1
9. Logarithms grow more slowly than any power of n log n = O(n^a) for any a>0 but n^a != O(log n)
10. n^a = O(bⁿ) for all a, b>1 but bⁿ != O(n^a) for b>1

Common examples of domination

Let X and Y denote variables and a,b,c, and d denote constants

In order of dominance (top is most dominant)

Log scale graph of big-O complexities

> 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):

Table of growth rates (12.1)

Note1: The value here is approximately the number of machine instructions executed by a 1 gigaflop computer in 5000 years.

Note 2: The value here is about 500 billion times the age of the universe in nanoseconds, assuming a universe age of 20 billion years.

Effect of Increased Computer Speed

Control Structures and Running Time Performance

if (condition)
       Stmt1
    else
       Stmt2

for (i=1; i<=n; i++)
     Stmt1

for (i=a; i<=b; i++){
    //body requiring constant time
}

for (i=a; i<=n; i++){
     //body requiring constant time
}

for (i=a; i<=n; i++){
   for(j=b; j<=n; j++){
      //body requiring constant time
   }
}

for (i=a; i<=n; i++){
      //body requiring O(M) time
   }

//---------------------------------------------------------------------- 
// 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²) O(n³)