Tutorial

Choosing the fastest algorithm for a certain task require that that you can estimate the runtime of an algorithm.

The absolute runtime of an algorithm is determined by several things, for example:

All these factors influence the actual runtime of a algorithm.

To compare the runtime behavior of algorithms is is important to have a mean to eliminate all these factors and to find a common description of the runtime.

It is common practice to compare the runtime of algorithms by their asymptotic runtime via the Big O notation. This notations describes how the runtime depends on the number of input elements. It answers the question how much does the runtime increase if I double the number of input elements?

With this notation an algorithm is said to have a O(n) runtime if the runtime increases linear with the number of input elements. It has O(n^2) if the runtime increases quadratic, etc.

Please help me to support this article:

Before posting questions, please see the vogella FAQ. If you have questions or find an error in this article please use the www.vogella.de Google Group. I have created a short list how to create good questions which might also help you.