Here you'll find some examples for big:

    // big O  
     _____
    /  _  \
    | / \ |
    | \_/ |
    \_____/

Some Functions

Evaluate the runtime of these functions!

Examples of O(1)

def func(n):
    return n*n
def func(n):
    for i in range(5000000000000):
        print(n)
def func(n):
    i = 50000000000000000
    while i > 10:
        print('wow this is going to run for a long time')
        print('it\'s still O(1) though!')
        i = i - 1

An example of O(n)

Notice that there's a loop that's dependent on n!

def func(n):
    s = 0
    for i in range(n): #in range n! 
        s += i
    return s

An example of O(n^2)

Notice that the loops are nested in this case. Meaning that we get n*n - or n^2 (:< iterations.

def func(n):
    s = 0
    for i in range(n):
        for j in range(n): #two range functions dependent on n
            s += j
    return s

An example of O(logn)

Binary search compares the target value to the middle element of the array.

def binary_search(alist, start, end, key):
    """Search key in alist[start... end - 1]."""
    if not start < end:
        return -1
    mid = (start + end)//2
    if alist[mid] < key:
        return binary_search(alist, mid + 1, end, key)
    elif alist[mid] > key:
        return binary_search(alist, start, mid, key)
    else:
        return mid

Proof of O(logn) runtime:

Let N be the number of items in our list.

Let x be the number of times we need to halve our list to get to our queried item.

Let lg(a) be the log with base 2 of the number a.

1/2^x is our factor that we 'divide' N by to get our 1 item.

Therefore 1 = N/2^x

2^x = N

lg(2^x) = lg(N)

xlg(2) = lg(N)

x = lg(N)

So the number of times we need to halve our list is lg(N)

Hence the runtime for binary search is O(log(n))

Fun with recursive functions

We need to trace these functions to determine their bigOh value.

Fibonacci Sequence

Fibonacci sequence written recursively.

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

Factorial

We should trace this recursive function to

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)