Analyzing Algorithms 4/6: Common Patterns of Growth

Some Common Patterns

When analyzing algorithms, there are several patterns that tend to appear over and over again. It is important to recognize these as they often lie at the heart of an optimized algorithm. Here we will look at a few of the most common patterns.

Hash Table Lookup (Constant)

A hash table is a datastructure that stores data as key / value pairs. Typically, a single data point can be inserted and subsequently accessed in constant time.

Binary Search (Logarithmic)

There are several different kinds of binary searches, but many exhibit a time complexity of O(lgn). Some O(lgn) examples include:

• searching a sorted set for a value (binary search)
• searching a balanced binary tree for a value (AVL tree, red-black tree, etc.)

Iteration / Loops / Nested Loops (Linear, Quadratic)

Iterating through a set of values is equivalent to a for loop which takes linear time. For each nested for loop grows the time complexity of the algorithm such that iterating through p nested for loops has a time complexity Θ(n^p).

Sorting (Super Linear)

There are many different sorting algorithms and they have different time complexities. However, sorting algorithms, such as Merge Sort and Heap Sort, that are optimized for the worst case scenario will have a time complexity of Θ(nlgn). Sometimes, an algorithm can perform much better on sorted input than non-sorted input. Therefore, some algorithms can be optimized by first sorting the input.

Note: In some situations where you can impose constraints on the input, it might be possible to have a better time complexity using non-comparison sorting algorithms like bucket sort or radix sort. However, without placing any constraints on the input, generally speaking, Θ(nlgn) is the time complexity for sorting.

Population Growth (Exponential)

The proverbial breeding rabbits exhibit growth in Θ(2^n). The first two rabbits spawn four rabits, which in turn spawn eight rabits, which spawn 16 rabits, and so on.

Permutations (Factorial)

Iterating over all the permutations of a set will take Θ(n!) time.