Example Algorithms of Different Orders

O(1): (Artificial) first_or_second

def first_or_second(lst):
    ''' Returns the larger of the first two elements in lst.
        Returns the second one if they are the same.
    '''
    if lst[0] > lst[1]:
        return lst[0]
    else:
        return lst[1]

Not artificial, and of great importance, the time to retrieve a value from a hash table or dictionary is constant and thus O(1). Thus Dictionaries are even faster than binary searches of lists (but require more memory — the classic tradeoff).

O(log n): Binary Search (see previous notes)

O(n): Finding the smallest value in a list

def min(lst):
    ''' Returns smallest value in lst.
        BUG: Fails on empty list.
    '''
    smallest = lst[0]
    for entry in lst[1:]:
        if entry < smallest:
            smallest = entry
    return smallest

O(n²): has_duplicates

def has_duplicates(lst):
    ''' Returns True if the list contains one or more pairs of duplicate values,
        and False otherwise.
        Compares each value to every value after it in the list checking for duplication.
    '''
    for i in range(len(lst)-1):
        for j in range(i+1, len(lst)):
            if lst[i] == lst[j]:
                return True
    return False

N.B. Nested loops usually indicate an order n² algorithm.

O(2ⁿ): Cryptarithm using brute-force search

Recall our first brute force approach to solving cryptarithms by trying all possible values. We had to let each letter be equal to each digit in turn, so for 4 letters we had 10×10×10×10 = 10⁴ possible solutions to evaluate, and for SEND+MORE=MONEY we had 10×10×10×10×10×10×10×10 = 10⁸ solutions. Finally for DONALD+GERALD=ROBERT we had 10¹⁰ solutions which took an impressive amount of time.

(For nitpickers: This is more precisely O(10ⁿ) but since 10 = 2^3.321928 that is O((2^3.321928)ⁿ)=O(2^3.321928n) so it is order of 2 to some power, and thus exponential.)

O(n!): Travelling Salesman Problem using brute-force search

The challenge of this famous problem is to find the shortest route for a travelling salesman who has a list of cities to visit and knows the distances between all pairs of them. If there are n cities, then there are n possiblities for the first city to visit. Having visited that one there are (n-1) choices for which city to visit second, (n-2) for the third visit, and so on down to 1 for the last city. Multiplying these possibilities gives a total of n×(n-1)×(n-2)×(n-3)×(n-4)×...×1 = n! possibilities to consider in total leading to an O(n!) algorithm. As we did with the cryptarithm problem you obviously want to cut down on the number of possibilities that have to be considered and there are many heuristics^* to do this, but there are no efficient algorithms for solving this problem. Wikipedia has more.

* a heuristic is a fast procedure that finds a good solution to a problem. Unlike an algorithm it is not guaranteed to find the best or even necessarily a correct solution.