Algorithm Efficiency

Last updated 2/11/05

Cost functions

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 based on cost functions of statement counts. 

Function dominance - a comparison of cost functions.  Note that  cost functions are functions that always grow.

The cost functions are typically using the size of the data collection as its domain, n.

Asymptotic dominance  

Cost functions are non-decreasing.  They're almost always purely increasing.

This is a comparison of cost functions when n is large.

Formally, function g asymptotically dominates function f if there are two positive constants c and n₀ such that

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

That is, "g asymptotically dominates f if c*g dominates f for all large values of n larger than n₀".

Or, "c*g(n) is always bigger than f(n) for values larger than n₀"

At some point, g(n) is always larger than f(n).  We're always interested if n₀ exists (otherwise g wouldn't dominate f). Sometimes we're interested in the value of  n₀. The value c is rather arbitrary and we're interested if we can find one.  It's particular value is rather useless. Different values of c may determine different n₀ .

Big-O Notation

We are trying to place functions into categories, so that when n is large the differences between the categories are striking, rather than almost linear.

The linear type of relationship between n and the cost is eliminated.

Defn: Given two nonnegative functions f and g,  f = O(g) if and only if g asymptotically dominates f

We say "f is of the order g" or "The order of f is g" or "f is big-Oh of 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²)

Proof. Let c = 4  and show that there exists an n₀ in which the equation holds.  There are lots of c's to choose from.  We're picking a value that larger than the coefficient of the highest degree term in the case of a polynomial.

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

so for c=4 we found n >= 5.  That is, we found a c and an n₀

Therefore, we can say O(n²) = 3n² + 3n + 10

Example 2

Here is an example where n may have to become  larger in order for g(n)=2ⁿ to dominate the polynomial f(n)=8n⁴.  We'll simply let c=1.

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

We can say O(2ⁿ)=8n⁴

Big-O Arithmetic

Here are some simplifications that can be applied

1. f = O(f) That is, a function can be its own order.

2. O(k*f) = O(f) That is, constants in the function can be ignored.

3. O(f+g) = Max[ O(f), O(g) ] That is, terms of lower degree can be ignored.

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

5. O(f/g) = O(f) / O(g)  same for a function that is a quotient

6. O(f) > O(g) if and only if f dominates g

7. Be careful with the rare 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

8. The powers of n are ordered according to the exponent n^a = O(n^b) iff a <= b

9. The order of log n is independent of the base taken log_a n = O(log_b n) for all a, b > 1

10. Logarithms grow more slowly than any power of n log n = O(n^a) for any a>0 but n^a != O(log n)

11. 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).  Realize that algorithms of higher dominance is bad!

We strive to get algorithm cost functions as small as possible (better performance). A "dominant" cost function is not better!

Dominate functions

Below are pairs of functions, determine which dominates the other. Also determine each function's big-O notation to give it order. [These exercises are borrowed from Headington/Riley, Data Abstraction and Structures Using C++, DC Heath, 1994. ]

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

Note1: The value here is approximately the number of machine instructions executed by a 1 gigaflop computer in 5000 years, or 5 years on a current supercomputer (teraflop computer)

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

The common thought is that if an algorithm runs at a particular speed and you need to increase the amount of data to be processed, just get a faster computer equivalent to the increase factor in the data size. 

This table shows for different algorithm complexities, just how much more data could be processed on a machine 1000 times faster.

Big-O Rankings

Rank the following big-O measures from greatest to least (worst to best performance). [These exercises are borrowed from Headington/Riley, Data Abstraction and Structures Using C++, DC Heath, 1994. ]

Classify each of the cost functions by name

Empirical Measurement

One method to measure running time of an algorithm against its input size is to place put timing points in the program.  This is TimeTester.java (from .../Programs/Chapter4)

import java.util.*;

public class TimeTester{

   public static void main(String[] args){
      long problemSize = 1000000;
      int work = 0;

      for (int i = 1; i <= 5; i++){ //run 5 times for average
         Date d1 = new Date();
         //change the blue code for other algorithms to measure
         for (int j = 1; j <= problemSize; j++){
            work++;
            work--;
         }
         Date d2 = new Date();
         long msec = d2.getTime() - d1.getTime();
         System.out.println("Problem size = " + problemSize + "\n" +
                            "Time in msec = " + msec);
         problemSize = problemSize * 2;
      }
   }

}

Control Structures and Running Time Performance

//the sequence
Stmt1;
Stmt2;

if (condition){
 Stmt1
} else {
 Stmt2

}

for (i=1; i<=n; i++){
 Stmt1
}
//while loops too, generally

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
 }

//----------------------------------------------------------------------
// This program prints all Pythagorean triples up through some user-
// specified value. All output triples are in increasing order.
//----------------------------------------------------------------------
import java.io.*;
public class pythag {
  public static void main()
  {
   int maxLen;
   int small;
   int next;
   int last;

   maxLen = Console.readInteger("Max. side length: ");
   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)
         System.out.println(small+", "+next+", "+last+"\n");
         last++;
       }
       next++;
     }
     small++;
   }
   System.exit(0);
}

Note that our big-Oh n is the program's maxLen--it's what the statement count depends on.

O(1) O(n) O(n²) O(n³)