time and space complexity of the following code:

Question

val = [5,6,7,8]
possible_combinations = [[]]
while val:
    person = val.pop()
    new_combinations = []
    for team in possible_combinations:
        new_combination = [person] + team
        new_combinations.append(new_combination)
    possible_combinations += new_combinations

Is it O(2^(n-1)) or O(n*(2^(n-1)))? I am confused between the above 2 complexity. Can anyone please give some input about the complexity?

Answer 1

Its Program for Calculating permutation using Iterative method Its time complexity will be O(N∗2^N)

Refer this code explanation for more details

https://www.educative.io/courses/grokking-the-coding-interview/gx2OqlvEnWG