Какова сложность этой программы Power Set?

Question

def powset2(seq):
    result = []
    if seq:
        head, tail = seq[:1], seq[1:]
        for smaller in powset2(tail):
            result.append(smaller)
            result.append(head + smaller)
    else:
        result.append([])
    return result
print((powset2([1,2,3,4])))

Поскольку мы проходим половину цикла, сложность logn?