Skip to content

Algorithms

Note

This section assumes that you have read the sections on values and types, testing, documentation and functions. Also, that you feel comfortable with assertions, function annotations and pytest. If you're not, then some of the code examples may be a bit difficult to follow. However, you can still understand a lot in this section without the code examples, it's just a good idea to have the knowledge of the other stuff too.

What is an algorithm

In mathematics and computing an algorithm is the procedure or formula for solving a problem based on performing a sequence of actions. In programming that could be a function that does a specific job every time it's called, or technically it could be an entire program. A good example of an algorithm would be a function for sorting all of the elements in a list, as lists often need to be sorted, but the method to sort a list alphabetically is the same every time no matter what list you are sorting as long as the data allows for it1.

If this isn't entirely clear then perhaps it's easier to think about algorithms as a series of steps. Think of it as all the steps needed to make your favourite beverage. If we were to make an algorithm to make my cup of coffee then I would need a series of steps something like this:

1 fetch a cup or clean the current one
2 check kettle water levels
3 if empty or low add more water
4 add coffee and sugar to cup 
5 fetch milk according to milk fetching algorithm 
6 add milk to cup
7 wait till kettle is boiled
8 fill cup with boiled water

As all of these steps happen every time I make a coffee, we can call this 'my_coffee_algorithm'. This also could be made more generic to account for every hot beverage, but regardless it could be considered a beverage algorithm. Whether an algorithm is generic or specific isn't as important as how efficient the algorithm is at the job it is trying to do. Not all algorithms are created equal and some will be much slower than others at doing specific tasks2.

Complexity

Another thing that can complicate an algorithms efficiency is how complex the task is to complete in the first place. Some algorithms will work just fine with small data sets, but as larger and larger sets of data are put into the same algorithm then it can heavily influence the time it takes to complete the task. Consider 'my_coffee_algorithm', for one cup of coffee it might be a fine algorithm to do the job, but what if I had to make 3 or 4 cups of coffee, it would take a lot longer making each one individually.

We express complexity with something called "big O notation" (pronounced big-ohh), which describes the worst case scenario for the algorithm and the data inputted, and then express that as a mathematical expression.

\(O(1)\)

This big O notation is representative of something that will always execute with the same amount of time no matter how big the input data is. This could be an algorithm that looks for the first entry in the data for instance, reading the first entry won't change the speed of the algorithm with a larger data set.

\(O(N)\)

This describes an algorithm who's complexity grows linearly with the size of the data that is passed to it. The algorithms worst case (\(O\)) grows with the amount of data that is passed to it (\(N\)). An example of this type of algorithm is trying to match a string to a list of strings. It could conceivably be matched to the first entry of course, but we always take the worst case scenario so if we assume that it always matches the last element of the list, the longer the list is the longer it would take, and hence the more complex.

\(O(N^2)\)

This describes an algorithm that raises in complexity directly proportional to the square of the data passed to it. This is commonly seen in algorithms with 2 nested conditions, as the data passed to the algorithm would need to be compared twice for each entry. If you had 3 nested conditions it would be \(O(N^3)\) and 4 nested conditions \(O(N^4)\), and so on.

\(O(2^N)\)

This describes an algorithm that doubles in complexity for each addition to the input data. The growth of an \(O(2^N)\) function is exponential3, starting very shallow with small data sets and rising very quickly the greater the input. A good example of a \(O(2^N)\) algorithms is a recursive function to calculate the next number in a sequence such as the Fibonacci sequence. Calculating a few numbers doesn't take much processing power but once you start calculating hundreds or thousands or tens of thousands of iterations of the sequence, even the most powerful of computers will feel the strain.

\(O(log N)\)

Logarithms in maths (the log N bit), can be kind of tricky for the uninitiated. A logarithm in it's simplest form is "how many of one number do we multiply to get another number". Using an example,

how many 2's do we need to get the number 8?

\(2 * 2 * 2 = 8\)

So...

\(log_2(8) = 3\)

You can also think of logarithms as being the opposite of exponents, as when you you do \(2^3 = 8\) you are doing essentially the opposite operation with a logarithm. For this example and more on logarithms you can find them at this site. A good example of an \(O(log N)\) algorithm is something like binary search algorithm (more on that below).

In binary search, the middle of a sorted data set is first found and compared to the value that you're looking for. If it is the same the search is finished, but if it is higher than the middle value we also know that the lowest half of the data set can be discarded. Then we do the same with the left over (the previous top half) of data, find the middle, compare the result, and disregard the unnecessary data. This means that it doesn't matter how large the data set is, the complexity growth will spike at first and then level out and plateau with larger data sets.

For some more information about 'big O' complexity and a look at algorithms that have been pre-calculated for their efficiency, you can check out the link here.

Searching and Sorting

The most frequent algorithms that are used in programming, especially when talking about efficiency, is searching and sorting algorithms. Both do much of what you would expect them to do by their namesake. Whether you are searching or sorting however, not every algorithm is created equal. Some algorithms work best on smaller data sets where as others work best on larger. Some searching algorithms are made specifically for unsorted data and others only work on sorted. It's important to know what your expected data set will be when you consider what algorithm to use. If you want to read more about how Python handles searching and sorting algorithms, and to get more information from another perspective with some additional optional exercises, you can read the python textbook docs here.

Searching algorithms

All searching algorithms have to be able to do one job... look through a chunk of data, and if the searched for value is matched to a value in the data set, tell you where it is in that data set or tell you that it isn't there. It could also conceivably return a True/False flag as to whether the data is there or not, but the process of search and comparison would still have to be the same for that algorithm, and wouldn't affect the efficiency of the algorithm.

The simplest searching algorithm, and the most intuitive to first understand, is the linear sort. To perform a linear sort all you do is take a value you are looking to find, and search through each index in an array of data to see if the data at that index location matches the the searched for value4. If they match then we have found our search value and can stop, the algorithm should be able to return the location of the matched value from the data set. In python we could implement a linear search with code something like this:

example-1.py from the beginning to the end 
#!/usr/bin/env python3
# Linear search algorithm 

def linear_search(data: list, value: int):
    """
    Performs a linear search on a passed data set.
    args:
        data    -> list, expecting a non empty list
        value   -> integer

    returns:
        integer -> the index of searched value. 
        OR
        str -> message detailing the lack of the searched value.   

    Gottchas:
        The for loops count from 1 but the index in a list 
        starts from 0. So we need to do a -1 in the if statement
        to match up the loop to the index location. 
    """

    assert isinstance(data, list) == True, "linear_search() data should be of type 'list'."
    assert data[0] != None, "linear_search() data list shouldn't be empty"

    search_value = int(value)   # casting to ensure the data is the expected type
    data_set = list(data)
    for i in data_set:
        # Uncomment this next print to see the counting as mentioned in the 'gottcha' docstring entry.
        # print('list counter:', i, '  index location:', i-1, '  Data at that location:', data_set[i-1])  
        if data_set[i-1] == search_value:
            return(int(i-1))
    else:
        return(f"Searched for value '{value}' is not in the dataset provided.")


def test_linear_search():
    """Just a custom test to prove it works... nothing to see here"""
    data = [1, 2, 3, 4, 5]
    data2 = [0]
    assert (linear_search(data, 1)) == 0, "Indexes should line up with values."
    assert (linear_search(data, 3)) == 2, "Indexes should line up with values."
    assert (linear_search(data, 6)) != 6, "This data shouldn't be contained in the list."
    assert (linear_search(data, 7)) == (linear_search(data, 7)), "Multiple runs of the same data should yield the same result."
    assert (linear_search(data2, 7)) != 7, "This data shouldn't be in the list."
    assert (isinstance(linear_search(data2, 5), str)) == True, "Fails should return the fail string." 


if __name__ == "__main__":
    data = [1, 2, 3, 4]
    data2 = [0]
    print(linear_search(data, 1))
    print(linear_search(data2, 7))

Example

This is quite a thorough example of how to write a linear search algorithm. It also includes some test code and asserts to enforce it's usage. At it's basic functionallity however, all we are doing is looping through a data set that is passed to the function and we are comparing each of the entries to a value we have asked the function to search for.

Because Linear search goes through each value in the list one-by-one, it is likely to take a long time to go through large data sets. The advantage of Linear Search is that it doesn't require ordered/sorted data in any way, it can even handle mixed data types.

What do you think is Linear Search's \(O\) complexity?
Algorithm best case expected worst case
Linear Search \(O(1)\) \(O(N)\) \(O(N)\)

In the best case scenario, linear search will find what it's looking for in the first index location. But we don't think of \(O\) complexity with the best case scenario in mind. We could expect that most cases of the algorithm will find their values somewhere in the middle of the data set, so the larger the data set the more iterations the algorithm has to go through. The worst case would be the algorithm finding the value in the very last index.

In both the worst and expected cases the complexity is \(O(N)\) because the complexity only gets worse the bigger the data set gets.

Extra Resources

http://sorting.at/ https://www.toptal.com/developers/sorting-algorithms https://www.youtube.com/watch?v=kPRA0W1kECg&ab_channel=TimoBingmann

  1. Obviously you would have to alphabetise strings, try alphabetically sorting numbers... it doesn't go well. ↩

  2. If you've ever gotten your younger sibling to make you a hot beverage you might have an inkling of what I mean. ↩

  3. Old man rant: Exponential growth is a specific mathematical term used to describe a growth that is directly proportional to the input data volume. Not the media abused version that just means 'more', but they wanted to resonate exponentially intelligent and so misapplied the denomination producing and perpetuating societal misinformation for their own paltry advantage... #sarcasticallytriggered. ↩

  4. If you're unsure about the terminology of this sentence then go to the 'basic data types' and 'stings and lists' sections to reread the terminology used in lists and data structures. ↩