Python: Big-O Analyses

[sophryu99]

Big-O : Big O is a formal notation that describes the behaviour of a function when the argument tends towards the maximum input.

As it reaches the right, it means it takes longer time. N is the size of the input

Data Structure Big-O Analyses

Sorting algorithms Bio-O Analyses

[sophryu99]

Constant time O(1)

No matter how many elements, it will always take x operations to perform.
Constant algorithms do not scale with the input size, they are constant no matter how big the input.

Example:

• addition: 1 + 2 takes the same time as 500 + 700
• They may take more *physical time, *but we do not add more steps in the algorithm for addition of big numbers.

Example in code

def OddOrEven(n):
    return "Even" if n % 2 else "Odd"

[sophryu99]

Logarithmic Time O(log(n))

A logarithmic algorithm halves the list every time it’s run.

Example:

• binary search

a = [1, 2, 3, 4, 5, 6 , 7, 8, 9, 10]

We want to find the number “2”.

We implement Binary Search as:

def binarySearch(alist, item):
    first = 0
    last = len(alist)-1
    found = False

    while first <= last and not found:
        midpoint = (first + last)//2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
            last = midpoint-1
            else:
                first = midpoint+1

    return found

Algorithm

• Go to the middle of the list
• Check to see if that element is the answer
• If it’s not, check to see if that element is more than the item we want to find
• If it is, ignore the right-hand side (all the numbers higher than the midpoint) of the list and choose a new midpoint.
• Start over again, by finding the midpoint in the new list.

The algorithm halves the input every single time it iterates. Therefore it is logarithmic.

Other examples:

• Fibonacci number calculations
• Binary Search Tree traversal

https://skerritt.blog/big-o/