Algorithms

At the highest level algorithms are either deterministic or probabilistic.

A deterministic algorithm is comparing files.

  1. Check the size.
  2. If that is the same, then check them each byte-by-byte until you fine a different byte or reach the end of each file.
  3. If nothing is different they are the same.

Probabilistic examples are bloom filters or a hashing algorithms.

BigO Notation Overview

In general, algorithms usually fall into the following performance classes: constant-time, logarithmic, linear, polynomial, exponential, and factorial.

  • Constant-time O(1): Random access in an array, insert in a linked list, lookup at a memory location. Simple comparisons are constant O(1).
  • Logarithmic O(log n): binary tree search. The log is typically 2. A binary search of sorted numerical data or a balanced tree, O(log n). The amount of time to execute the algorithm is the log of the input size.
  • Linear O(n): Finding an item in a linked list, searching an unordered list, basic operations on n members O(n) where you have to operate on every element in an input set.
  • Polynomial O(n^k): Where k is a constant and n changes. This is a feasible computation. Convolutions, Discrete Fourier transform, many types of sorts O (n^2).
  • Exponential O(k^n): Where k is a constant and n increases, like binary numbers 2^2, 2^3, 2^4, 2^5, etc..
    This quickly becomes unsolvable.
  • Polynomial vs. Exponential explained.
  • Factoral: O(n!) Traveling salesman, dictionary attacking, password cracking. For example, you have 5 items and want to compare all of the permutations: !5 = 5 * 4 * 3 * 2 * 1 = 120. Brute force permutations are factorial, O(n!).
  • http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
  • http://www.daveperrett.com/articles/2010/12/07/comp-sci-101-big-o-notation/
  • Beginner’s Guide to BigO Notation
  • Logarithms and Exponents in Complexity Analysis
  • http://en.wikipedia.org/wiki/Logarithm
  • http://en.wikipedia.org/wiki/Computational_complexity_theory
  • http://en.wikipedia.org/wiki/Asymptotic_analysis
  • http://en.wikipedia.org/wiki/Asymptotic_curve
  • http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html
  • http://www.daveperrett.com/articles/2010/12/07/comp-sci-101-big-o-notation/
  • http://www2.hawaii.edu/~janst/211/lecture/BigO.htm

Concepts Related to Algorithms and Searches

Tail Recursion

Tail recursion is coding the call to an recursive function so that the return value of the recursive call is immediately returned to the calling code. This enables for optimization in the compilation to avoid pushing an extra function call on the stack and can help to eliminate stackoverflow problems.

The following is tail recursive as the final call in the function is to return the value of the recursive call:

int f(int x, int y) {
  if (y == 0) {
    return x;
  }

  return f(x*y, y-1);
}

The following is NOT tail recursive as there is an operation performed by the result of the recursive call before returning a value to the calling frame.

int g(int x) {
  if (x == 1) {
    return 1;
  }

  int y = g(x-1);

  return x*y;
}

Tractability

So-called easy, or tractable, problems can be solved by computer algorithms that run in polynomial time; i.e., for a problem of size n, the time or number of steps needed to find the solution is a polynomial function of n. Algorithms for solving hard, or intractable, problems require times that are exponential.