educative.io

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

Courses
,
#1

There are two loops in the code. First loop executes 2^n times. the inter loop execute n times. Then time complexity is O(2^n * n) not O(2^n) ? Am I miss anything?

And also for the space complexity. we only create new hashset in the for loop. after every loop execute, hashset space will be garbage collected and reused. and every hashset has maximum n integers. So space complexity should be O(n).

1 Like
#2

Hi Franklin,

Thank you for reaching out! We are looking into this problem and will get back to you soon!

Regards,
Team Educative

#4

Hi Franklin,

Thanks for the correction here as the time complexity of given problem is O(2^n * n) as you said. But for space complexity which is maximum amount of space used at any time in the program, so when in the for loop we used the Hashset then we need the maximum amount of memory which eventually computes the space complexity to O(2^n * n) not O(n).