Algorithms For Dummies

 

»

Cubic complexity O(n

3

): Operations grow even faster than quadratic 

complexity because now you have multiple nested iterations. When an 

algorithm has this order of complexity and you need to process a modest 

amount of data (100,000 elements), your algorithm may run for years. When 

you have a number of operations that is a power of the input, it is common to 

refer to the algorithm as running in polynomial time.

 

»

Exponential complexity O(2

n

): The algorithm takes twice the number of 

previous operations for every new element added. When an algorithm has 

this complexity, even small problems may take forever. Many algorithms 

doing exhaustive searches have exponential complexity. However, the classic 

example for this level of complexity is the calculation of Fibonacci numbers 

(which, being a recursive algorithm, is dealt with in Chapter 5).