Algorithms For Dummies

 

»

Linear complexity O(n): Operations grow with the input in a 1:1 ratio. A 

typical algorithm is iteration, which is when you scan input once and apply an 

operation to each element of it. Chapter 5 discusses iterations.

 

»

Linearithmic complexity O(n log n): Complexity is a mix between logarith-

mic and linear complexity. It is typical of some smart algorithms used to order 

data, such as Mergesort, Heapsort, and Quicksort. Chapter 7 tells you about 

most of them.

FIGURE 2-1: 

Complexity of an 

algorithm in case 

of best, average, 

and worst  

input case.

---

CHAPTER 2

  Considering Algorithm Design 

     41

 

»

Quadratic complexity O(n

2

): Operations grow as a square of the number of 

inputs. When you have one iteration inside another iteration (nested itera-

tions, in computer science), you have quadratic complexity. For instance, you 

have a list of names and, in order to find the most similar ones, you compare 

each name against all the other names. Some less efficient ordering algo-

rithms present such complexity: bubble sort, selection sort, and insertion sort. 

This level of complexity means that your algorithms may run for hours or 

even days before reaching a solution.