Reputation: 43
I am currently practicing for an upcoming interview but still have a hard time analyzing big O worst-time complexity for recursive functions. For example, I have this code below where the answer seems to be O(n*2^n) but I don't know why this is the case. If anything, I thought the time complexity would be O(n * n^n) since the loop is O(n) and the decision tree is expanding like the picture I have drawn below (please excuse my bad drawing). At the first level of the decision tree here, shouldn't it be expanding n times and the height of the tree is also n making it n^n?
s = "aab"
result = []
def dfs(index: int, curr: list) -> None:
#Base cases:
if index == len(s):
result.append(curr[:])
return
else:
word = ""
for i in range(index, len(s)):
word += s[i]
curr.append(word)
dfs(i + 1, curr)
curr.pop()
dfs(0, [])
print(result)
Upvotes: 1
Views: 60