What is Big Oh?

The term big oh is a commonly used when discussing the runtime of a function. For example, if I have a function that takes 10 steps when given an input size of 10, 20 steps for an input size of 20, and so on; then, when given a large arbitrary input size of n, it would take n steps. This function would be denoted as O(n) because the function grows linearly. Therefore, big oh is denotes the runtime of a function. However, the runtime can be different for different inputs. In CSC108, we learned about bubble sort. Here is a code for bubble sort we used in CSC108:

def bubble_sort(L):

    """ Sort the items of L from smallest to largest.  """

    end = len(L) - 1

    while end != 0:

       for i in range(end):

            if L[i] > L[i + 1]:

                L[i], L[i + 1] = L[i + 1], L[i]

        end = end - 1

The algorithm of bubble sort is based on a simple technique, where two consecutive numbers are compared with each other and swapped iff the second number is smaller than the first. This is done for each number in the list, indicating that the runtime of an unsorted list would be O(n²). However, the runtime can be totally different if the list was already sorted (the runtime would be O(1)), which would be the best case scenario. Often the best case scenario doesn’t tell us much, so we look at the worst case scenario, which is when the list is reversed sorted in the bubble sort example. The O(n²) is the worst case runtime for bubble sort, which is useful to know to get an idea about the function’s efficiency (the topic of my next assigned slog post).