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

3.1. Resources

Big O Notation - Wiki

If you need more assistance we offer Online Training and Onsite training as well as consulting

See License for license information.