Big O notation & Logrithms

gistfile1.txt

##Big O notations - of algorithms

Big O describes the worst case scenario, can be used to define execution time or space used (e.g. in memory or on disk) by an algorithm.

////////////////////////////////////////////////////////////////////////////////////////////////////////////////
O(1)
executes in same time or space regardless of size of the input data

vals = [None,'jack','and','jill']


def is_first_element_null(ds):
    return ds[0] is None

print(is_first_element_null(vals))

# O/P
True
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
O(N)
O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. The example below also demonstrates how Big O favours the worst-case performance scenario; a matching string could be found during any iteration of the for loop and the function would return early, but Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.

vals = [None, 'jack', 'and', 'jill']


def contains_value(ds, value):
    for val in ds:
        if val == value:
            return True
    return False

print(contains_value(vals, 'jill'))

# O/P
True
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
O(N^2) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N^3), O(N^4) etc.

vals = [None, 'jack', 'and', 'jill', 'jack']

def contains_duplicates(ds):
    for outer_id, outer_value in enumerate(ds):
        for inner_id, inner_value in enumerate(ds):
            if outer_id == inner_id:
                continue
            if ds[outer_id] == ds[inner_id]:
                return True
    return False


print(contains_duplicates(vals))

# O/P
True
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
O(2^N)

O(2^N) denotes an algorithm whose growth doubles with each additon to the input data set. The growth curve of an O(2N) function is exponential - starting off very shallow, then rising meteorically. An example of an O(2N) function is the recursive calculation of Fibonacci numbers:

def fibonacci(number):
    if number <= 1:
        return number
    return fibonacci(number - 2) + fibonacci(number - 1)


print(fibonacci(20))

# O/P
6765
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
##Logrithms
O(log N)
Binary Search Algorithm
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
more info on :
http://bigocheatsheet.com/
https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/