I received a practice exam for an upcoming midterm, but it does not have the answers. One of the questions I am unsure of is asking for the time complexity of the following function
def f6(n):
if n > 9:
return 1
else:
x = 1
for i in range(0,n):
x+= f6(n+1)
return x
please help
How do you get the exponential O(2^n)? The classic exponential function would be:
def exp(n):
if n <= 0:
return 0
return 1 + exp(n - 1) + exp(n - 1)
if __name__ == "__main__":
for n in range(10):
assert 2**n - 1 == exp(n)
That is, two sub-calls per frame, creating a binary tree call stack shape, with lots of repeated work.
While the binary form is common, the generalization of this pattern is O(k^n):
def exp(n, k):
if n <= 0:
return 0
total = 1
for _ in range(k):
total += exp(n - 1)
return total
This bears some resemblance to f6 which looks like it could be O(n^n): every call does O(n) work and spawns n child frames recursively.
But f6 is O(1). How do we get that? First, remove the irrelevant information:
def f6(n):
if n > 9:
return
for _ in range(n):
f6(n + 1)
The critical part is the base case if n > 9: return. This puts a limit on growth, which is exactly the thing Big O measures. For any value greater than some constant (9, in this case), we have no increase in the amount of work relative to n and we're left with O(1).
It's counterintuitive, but if the base case were if n > 10e50: return rather than 9, it'd still be O(1). That 10e50 is still a constant factor, which Big O ignores, as unrealistic as it may seem. Big O is a theoretical growth/scalability heuristic, not a measure of the realistic work that might be done by an algorithm.
Also important is to consider negative values of n to ensure that decreases of n don't result in growth. for _ in range(n): sets the constraint that negative numbers up to and including 0 won't run the loop block where the recursion happens, so we're safe.