Algorithm Efficiency

Performance

Two areas are important for performance:

  1. space efficiency - the memory required, also called, space complexity
  2. time efficiency - the time required, also called time complexity

Space Efficiency

There are some circumstances where the space/memory used must be analyzed. For example, for large quantities of data or for embedded systems programming.

Components of space/memory use:

1. instruction space Affected by: the compiler, compiler options, target computer (cpu)
2. data space Affected by: the data size/dynamically allocated memory, static program variables,
3. run-time stack space Affected by: the compiler, run-time function calls and recursion, local variables, parameters

The space requirement has fixed/static/compile time and a variable/dynamic/runtime components. Fixed components are the machine language instructions and static variables. Variable components are the runtime stack usage and dynamically allocated memory usage.

One circumstance to be aware of is, does the approach require the data to be duplicated in memory (as does merge sort). If so we have 2N memory use.

Space efficiency is something we will try to maintain a general awareness of.

Time Efficiency

Clearly the more quickly a program/function accomplishes its task the better.

The actual running time depends on many factors:

Time Efficiency - Approaches

When analyzing for time complexity we can take two approaches:

  1. Order of magnitude/asymptotic categorization - This uses coarse categories and gives a general idea of performance. If algorithms fall into the same category, if data size is small, or if performance is critical, then the next approach can be looked at more closely.
  2. Estimation of running time -
    By analysis of the code we can do:
    1. operation counts - select operation(s) that are executed most frequently and determine how many times each is done.
    2. step counts - determine the total number of steps, possibly lines of code, executed by the program.

    By execution of the code we can:
    1. benchmark - run the program on various data sets and measure the performance.
    2. profile - A report on the amounts of time spent in each routine of a program, used to find and tune away the hot spots in it. This sense is often verbed. Some profiling modes report units other than time (such as call counts) and/or report at granularities other than per-routine, but the idea is similar (from foldoc).
      Look at the info entry for gprof on one of the linux machines.

Time Efficiency - Three Cases

For any time complexity consideration there are 3 cases:

  1. worst case
  2. average case
  3. best case

Usually worst case is considered since it gives an upper bound on the performance that can be expected. Additionally, the average case is usually harder to determine (its usually more data dependent), and is often the same as the worst case. Under some circumstances it may be necessary to analyze all 3 cases (algorithms topic).

Big-O Notation

Order of magnitude/asymptotic categorization eliminates hardware from consideration and expresses efficiency in terms of data size, N.

There are several definitions which all work in a similar manner. Also there are some Greek letters involved which are unrepresentable in HTML at this point and so are spelled out.

Order of magnitude/asymptotic categorization ignores coefficients and is based on larger values of N and so if coefficients are large or values of N are small the behavior may be different from expected.

Big-O -
f(n) = O(g(n)), read as f of n is big oh of g of n, iff (if and only if) positive constants c and n0 exist such that f(n) <= cg(n) for all n, n >= n0.

Since the higher order term dominates the lower order terms in an algebraic expression for large N, the low order terms can be ignored. Thus the following functions are be used.

Big-O Categories

Function Big-O Name
1 O(1) constant
log n O(log n) logarithmic
n O(n) linear
n log n O(n log n) n log n
n2 O(n2) quadratic
n3 O(n3) cubic
2n O(2n) exponential
n! O(n!) factorial

Big-O Examples

Example:

 5n + 7 <= 5n + n       for n >= 7
        <= 6n

So c = 6 and n0 = 7 thus 5n + 7 is O(n).

 

 

Example:

 3n2 + 4n <= 3n2 + n2   for n >= 4
          <= 4n2

So c = 4 and n0 = 4 thus 3n2 + 4n is O(n2).

 

 

 

It is usually assumed the bound is tight. For example, 3n + 4 function is bounded by n2 for n > 4 and so is O(n2). This is not a tight bound however, 3n + 4 is O(n).

Other Categories

Omega -
f(n) = omega(g(n)), read as f of n is omega of g of n, iff (if and only if) positive constants c and n0 exist such that f(n) >= cg(n) for all n, n >= n0.
Theta -
f(n) = Theta(g(n)), read as f of n is theta of g of n, iff (if and only if) positive constants c1, c2, and n0 exist such that c1g(n) <=f(n) <= c2g(n) for all n, n >= n0.
Little-O -
f(n) = o(g(n)), read as f of n is little oh of g of n, f(n) = O(g(n)) and f(n) != omega(g(n))

slides