-
-
Save DomNomNom/17e808a6e3fc61ac3bf3 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # 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