Complexity Analysis. The following article describes the theoretical background on evaluating the performance of algorithms and programs.
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.
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.
|TRAINING||SERVICE & 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-2016 vogella GmbH. Free use of the software examples is granted under the terms of the EPL License. This tutorial is published under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Germany license.