• O(1) Constant time algorithms: Algorithms that perform the same amount of work regardless of the size of the input set n.
  An example of a O(1) algorithm would be to display the first element of a list.
• O(lg n) Logarithmic time algorithms: Algorithms whose work performed is proportional to the lg base 2 of the size of the input set n.
  An example of a logarithmic algorithm would be binary search.
• O(n) Linear time algorithms: Algorithms whose work performed is proportional to the size of the input set n.
  Examine-all algorithms are typically linear algorithms.
  An example of a linear algorithm would be sequential search.
• O(n lg n) N-Log N algorithms: Algorithms whose work performed is proportional to the size of the input set n multiplied by lg base 2 of n
  An example of an N-Log N algorithm would be mergesort.
• O(n²) Quadratic time algorithms: Algorithms whose work performed is proportional to the square of the size of the input set n.
  All-pairs algorithms are typically quadratic algorithms.
  An example of a quadratic algorithm would be selection sort.
• O(n³) Cubic time algorithms: Algorithms whose work performed is proportional to the cube of the size of the input set n.
  Algorithms with triple-nested for/while loops are typically cubic.

• O(2ⁿ) Exponential (or worse) time algorithms: Algorithms whose work performed is proportional to an integer raised to the power of n, where n is size of the input set.
  An example of a exponential algorithm would be the brute force algorithm used to solve the ``Road Trip'' problem (i.e. The Traveling Salesman Problem).

Additionally, algorithms, or the problems that the algorithms solve can be classified by:

• Tractable: Algorithms whose running time is ``reasonable.'' Any algorithm whose running time is expressed as a polynomial in n is tractable. (e.g. Cubic, quadratic, logarithmic)
• Intractable: Algorithms whose running time is ``unreasonable.'' Any algorithm whose running time is expressed as an exponential function of n is intractable. (e.g. O(2ⁿ).

  • Some intractable problems are known to be intractable. It can be shown that it is impossible to solve these problems with a tractable algorithm.
  • For many intractable problems, while the best known algorithm for solving the problem is intractable, it is unknown whether a tractable algorithm exists, or if it can be shown that it is impossible to solve the problem with a tractable algorithm. (The P=NP question.)

• Unsolvable: Problems for which a mathematical proof exists that no algorithm can possibly exist to solve this problem. The ``Halting Problem'' is the canonical example of a problem in this category. Not all mathematical problems can be solved by an algorithm.