big.py

# a recursive function that produces big numbers. What is the time complexity of this?
def big(a, b, depth):
    if depth == 0:
        return a*b  # assume this takes one unit of time

    out = 1
    for i in xrange(b):  # repeat the following b times
        out = big(a, out, depth-1)
    return out


#
# some results of big():
# big(3, 2, 2): 27,
# big(8, 2, 2): 16777216,
# big(2, 4, 2): 65536,
# big(3, 3, 2): 7625597484987,
# big(2, 5, 2): number with 19729 digits

# number of multiplications in big():
# mults(3, 2, 2): 4,
# mults(8, 2, 2): 9,
# mults(2, 4, 2): 23,
# mults(3, 3, 2): 31,
# mults(2, 5, 2): 65559,

# Question: 
#  Is it possible to evaluate mults(a,b,d) without evaluating big(a,b,d)?
#  Note: evaluating big() with smaller arguments would be acceptable, but we want to avoid counting multiplications