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.
Appendix A: Copyright, License and Source code
Copyright © 20122018 vogella GmbH. Free use of the software examples is granted under the terms of the Eclipse Public License 2.0. This tutorial is published under the Creative Commons AttributionNonCommercialShareAlike 3.0 Germany license.