Home Tutorials Training Consulting Products Books Company Donate Contact us

Online Training

Quick links


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.

3. About this website

4. Links and Literature

4.2. vogella GmbH training and consulting support


The vogella company provides comprehensive training and education services from experts in the areas of Eclipse RCP, Android, Git, Java, Gradle and Spring. We offer both public and inhouse training. Whichever course you decide to take, you are guaranteed to experience what many before you refer to as “The best IT class I have ever attended”.

The vogella company offers expert consulting services, development support and coaching. Our customers range from Fortune 100 corporations to individual developers.

Copyright © 2012-2018 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 Attribution-NonCommercial-ShareAlike 3.0 Germany license.

See Licence.