def binom_naive(n, k):
    if k == n or k == 0:
        return 1
    if n < k or n < 0 or k < 0:
        return 0
    return binom_naive(n - 1, k - 1) + binom_naive(n - 1, k)

%timeit -n 3 binom_naive(6,4)

%timeit -n 3 binom_naive(26,4)

%timeit -n 3 binom_naive(26,13)

binom_memory = {}

def binom_mem(n, k):
    if k == n or k == 0:
        return 1
    if k > n or n < 0 or k < 0:
        return 0
    key = (n,k)
    if key not in binom_memory:
        binom_memory[key] =  binom_mem(n - 1, k - 1) + binom_mem(n - 1, k)
    return binom_memory[key]

%%timeit -n 3 
binom_memory.clear()
binom_mem(6,4)

%%timeit -n 3 
binom_memory.clear()
binom_mem(26,4)

%%timeit -n 3 
binom_memory.clear()
binom_mem(26,13)

%%timeit -n 3
binom_mem(26,13)

def binom_formula(n,k):
    return factorial(n) // (factorial(k) * factorial(n - k))

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

%timeit -n 3 binom_formula(6,4)

%timeit -n 3 binom_formula(26,4)

%timeit -n 3 binom_formula(26,13)

%timeit -n 100 binom_naive(14,5)
%timeit -n 1000 binom_formula(14,5)
%timeit -n 1000 binom_mem(14,5)

%timeit -n 1 binom_naive(24,8)
%timeit -n 10 binom_formula(24,8)
%timeit -n 10 binom_mem(24,8)

def pascal(n):
    for i in range(n + 1):
        for j in range(i + 1):
            print(binom_mem(i,j), end="\t")
        print()

pascal(4)

pascal(7)

def count_change(amount, coins):
    if amount == 0:
        return 1
    if amount < 0 or len(coins) == 0:
        return 0
    without_large_coint = count_change(amount, coins[:-1]) 
    with_large_coin = count_change(amount - coins[-1], coins)
    return without_large_coint + with_large_coin

count_change(5, [1,2,3])

def slowsort(lst):
    """quicksort of list lst"""
    if len(lst) <= 1: 
        return lst
    pivot = lst[0]      # select first element from list
    smaller = [elem for elem in lst if elem < pivot] 
    equal = [elem for elem in lst if elem == pivot]      
    greater = [elem for elem in lst if elem > pivot]
    return slowsort(smaller) + equal + slowsort(greater)

import random

def quicksort(lst):
    """quicksort of list lst"""
    if len(lst) <= 1: 
        return lst
    pivot = random.choice(lst) # select a random element from list
    smaller = [elem for elem in lst if elem < pivot] 
    equal = [elem for elem in lst if elem == pivot]      
    greater = [elem for elem in lst if elem > pivot]
    return quicksort(smaller) + equal + quicksort(greater)

lst = [random.randint(0,100) for _ in range(100000)]

%timeit -n 10 slowsort(lst)

%timeit -n 10 quicksort(lst)

lst = [i for i in range(100)]

%timeit -n 10 slowsort(lst)

%timeit -n 10 quicksort(lst)