Big-O Analysis

What is best (lowest) big-O bound for each of the following functions?
- $f(n) = 17 + 3n + 21 n^2$
- $g(n) = n(2n+2)$
- $h(n) = n^8 + n^4 + 2^n$
- $j(n) = n^2 \log(n) + 8n^2$

For each of the following functions, determine their best (lowest) worst case big-O complexity as a function of n:

    def f1(n):
        c = 0
        step = n
        while step>1:
            step/=2
            c++
        return c

    def f2(n):
        int c = 0
        for i in range(n):
            for j in range(n):
                for k in range(10):
                    c++
        return c

    def f3(n):
        c = 0
        for i in range(n):
            int s = n
            while(s>1):
                s/=2
                c++
        return c

    def f4(n):
        c = 0
        for i in range(n):
            for j in range(i):
                c++
        for k in range(n):
            c++
        return c

    def insertion_sort(array):
        for i in range(1, len(array)):
            temp = array[i]
            position = i
            while position > 0 and array[position-1] > temp:
                array[position] = array[position-1]
                position-=1
            array[position]=temp

    def bubble_sort(array):
        for passes in range(len(array)-1, 0, -1):
            for i in range(passes):
                if array[i]>array[i+1]:
                    array[i],array[i+1] = array[i+1],array[i]

Challenge problems

What is the best (lowest) big-O bound for each of the following functions?

$k(n) = \sum_{x=0}^n 2^x$
$i(n) = \sum_{x=0}^n x$

    def f5(n):
        if n is 0:
            return 1
        return 1 + f5(n-1) + f5(n-1)

    def f6(n):
        if n is 0:
            return 1
        c = 0
        for i in range(n):
            c = c + f6(i)
        return c

    def merge_sort(array):
        if len(array) == 1:
            return array
        mid = len(array)//2
        left = merge_sort(array[:mid])
        right = merge_sort(array[mid:])
        result = []
        while (0 < len(left)) and (0 < len(right)):
            if left[0] > right[0]:
                result.append(right[0])
                right.pop(0)
            else:
                result.append(left[0])
                left.pop(0)
        return result + y + z # For any elements left over