Sir Absolute 0
Sir Absolute 0

Reputation: 43

Why is this function time complexity O(n*2^n)?

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)

enter image description here

Upvotes: 1

Views: 60

Answers (0)

Related Questions