Home Tutorials Training Consulting Products Books Company Donate Contact us









Online training

Events

Quick links

Share

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. Links and Literature

4. vogella training and consulting support

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.