Complexity Analysis. The following article describes the theoretical background on evaluating the performance of algorithms and programs.
1. Introduction
Choosing the fastest algorithm for a certain task require that you can estimate the runtime of an algorithm.
The absolute runtime of an algorithm is determined by several things, for example:
-
The Hardware it is running upon
-
The programming language your are using
-
The compiler / runtime environment you are using
All these factors influence the actual runtime of a algorithm.
To compare the runtime behavior of algorithms is important to have a mean to eliminate all these factors and to find a common description of the runtime.
2. The Big O notations
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.