induction.py

# Prove that the cost of this function is O(n)
#
# Prove that this function computes a result x' such that:
#      x' = x * (x+1) / 2
def e(x):
    if (x == 0): return 0
    return: x + e(x - 1)

# Prove that the return value of this function is a list l' such that:
#    forall i < len(l). l'[i] = 2 * l[i]
def g(l):
    if (l == []):
        return []
    else:
        return [2 * head(l)] + g(tail(l))


# Prove the running time (cost) of the following function is O(log(n))
# This is trickier than you would usually see, and won't be on the exam, 
# the basic idea is to perform an inductive that shows cost of 
# f(2*x) = 1 + cost of f(x), which you can then use to establish what you want.
def f(x):
    if (x <= 1):
        return 1
    else:
        return f(x / 2)

# Question:
# Assuming,
#   - head(l) takes O(1)
#   - tail(l) takes O(n)
# Does min(l) cost (give the tightest bound you can):
#   - O(n)
#   - O(n^2)
#   - O(2^n)
#
# Prove: min(l) returns an element e such that e is in the list l and
# for all i < len(l), e <= l[i]
#
def min(l):
    if (head(l) < min(tail(l))):
        return head(l)
    else:
        return min(tail(l))