Home Tutorials Training Consulting Books Company Contact us


Get more...

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 you 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.

3. Links and Literature