CODEWITHSUNDEEP
pythonbig-o
Zercon
Zercon

Reputation: 135

Why does this function have exponential complexity big O instead of quadratic?

The following function has been given:

def genSubsets(L):
    res = []
    if len(L) == 0:
        return [[]]
    smaller = genSubsets(L[:-1])
    extra = L[-1:]
    new = []
    for small in smaller:
        new.append(small+extra)
    return smaller+new

From my understanding, i making a copy of a list is (O n), then looping is (O n) as well. Which should make this (O n^2). However, it seems that my logic is flawed and the answer is (O 2^n). Why?

Upvotes: 0

Views: 55

Answers (1)

templatetypedef
templatetypedef

Reputation: 372942

From my understanding, i making a copy of a list is (O n)

You are correct that making a copy of a list of n items takes time O(n). And in this case, each of the lists that's being copied is a subset of the original list, which has length n, so each list copied does take time O(n).

then looping is (O n) as well

Looping over a list of length n takes time O(n). However, in this case, the lists that you're looping over do not have n elements in them. There are 2n subsets of a set of size n, so at the top-level recursive call, when you recursively generate all subsets of L[:-1], you will end up with a list of 2n-1 items. Looping over that list takes time O(2n).

More generally, when looking at a loop or a list, it's important to ask "how many times does this loop run?" or "how many elements are in this list?"

Upvotes: 2

Related Questions