Algorithm Notes – Classification of Algorithms

References used for this section: C

Algorithms usually have a primary parameter which we will call N. This is basically the input size (i.e the number of data items to be processed) and can be anything like:

  • The degree of a polynomial
  • The size of a file on which sorting or searching needs to be done
  • The number of nodes in a graph etc.

Algorithms can be classified with to the functions their running times are proportional to. Most common algorithms have running times proportional to one of the following functions (in descending order of efficiency):

  1. Constant. All the instructions in the algorithm are executed once or at most a few times. (define ‘a few’ precisely?) These algorithms are the most efficient.
  2. Logarithmic ( log N ). When N doubles, the running time of these algorithms increase by a constant. When N increases to N^2, the running time doubles.
  3. Linear ( N ). When N doubles, the running time doubles also.
  4. Log-Linear ( N log N ). When N doubles, the running time more than doubles (but only slightly).
  5. Quadratic ( N^2 ). When N doubles, the running time quadruples.
  6. Cubic ( N^3 ). When N doubles, the running time increases eight times.
  7. Exponential ( 2^N ). When N doubles, the running time squares. These are hopelessly slow algorithms.

To summarise, the running time of common algorithms is usually an element of:

  • \mathcal{O}(c)
  • \mathcal{O}(log N)
  • \mathcal{O}(N log N)
  • \mathcal{O}(N)
  • \mathcal{O}(N^2)
  • \mathcal{O}(N^3)
  • \mathcal{O}(2^N).

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s