Are O(n*2^n) and O(2^n) same? Whats the complexity of this program?

Question

Hi, i wrote this program for generating powerset of a list, using recursion in python.
https://code.sololearn.com/cPM3De7f0Tjn

I cant figure out whats the complexity of this program? I see that there are n recursion steps to break list into 1 element, that seem like a linear function to me.

Now at each recursion steps i am iterating over generated subsets, which increase by factor of 2^n at each step. in final steps the factor is almost equal to 2^n so i assume that complexity is 2^n, and that is nested under n recursion steps, so that should be n*2^n? Or it should be just written as 2^n? If yes, then why do we not ignore n or log(n) in n*log(n).

Also if i use this function in another function where I loop n times and at each loop i generate power set of same list of n elements, what would be the complexity of that? Thank you for taking time to help me :)

Answer 1

Let's say f(n) is the number of operations the code needs for a list of size n. Now your subset() function has two main things:

a. It calls itself with a list of size n-1 (which by definition has f(n-1) ops)
b. It iterates over the collection of all sublists of a list of size n-1. That collection has 2^(n-1) elements. So

f(n) ~ f(n-1) + C 2^(n-1)

where C is a constant. But we can again replace f(n-1) by f(n-2) + C 2^(n-2), and so on... Thus

f(n) ~ f(1) + C (2^1 + 2^2 + ... + 2^(n-2) + 2^(n-1))

Summing the geometric progression,
f(n) ~ C 2^n, and so the complexity is O(2^n).

Regarding your other question: no, O(2^n) and O(n*2^n) are by no means the same. By definition, for a positive valued function g, we say f(x) is O(g(x)), if there's an M>0 such that for all sufficiently large x,
|f(x)| <= M*g(x)

Now, can there exist an M (fixed) such that n*2^n <= M*2^n for ALL large n? No, as whatever M we choose, it will not hold for n=M+1. So n*2^n, which is obviously O(n*2^n), is not O(2^n).

Answer 2

Thanks! Yes, you are right about everything. If we define a function that generates the power set of n elements n times, it would have n * f(n) operations, and the complexity would be O(n * 2^n).

Answer 3

Kishalaya Saha wow, that was a different angle to look at the problem and it really helped me to visualise the concept better, and how n*2^n is different than 2^n, so basically we are having 2^n coz its becoming a gp, if we had (2^n + 2^n + ..... n times), that would have been n*2^n ? also can you give me an example of that complexity please? is the function i mentioned about in the last part of my question of that complexity? coz, there i am doing 2^n steps n times? Thank you :)