Skip to content

Instantly share code, notes, and snippets.

Created August 1, 2014 11:34
Show Gist options
  • Save anonymous/236b03db3a0f135f7333 to your computer and use it in GitHub Desktop.
Save anonymous/236b03db3a0f135f7333 to your computer and use it in GitHub Desktop.
Finding time complexity of a function that produces numbers that are way too big.
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment