# Time complexity of powerset algorithm

posted 3 years ago

Just warming it up before my sem-IV Algorithms class , I have written a algorithm for power-set written as p(a) which i guess every 1 here aware of...

just learning about time complexities of algorithms (Big-Oh) , & correct me if i am wrong ...

algorithm:

Time complexity O(n)*O(n) = O(n^2) is it correct?if no , please explain ....thanks

just learning about time complexities of algorithms (Big-Oh) , & correct me if i am wrong ...

algorithm:

Time complexity O(n)*O(n) = O(n^2) is it correct?if no , please explain ....thanks

The Only way to learn is ...........do!

Visit my blog http://inaved-momin.blogspot.com/

Mike Simmons

Ranch Hand

Posts: 3028

10

posted 3 years ago

Now the code is complete . and This iteration increases as the no. of element in pw increases for eg:

initially pw contains just " " then 1 then 2 & 12 assume int[] a {1,2} ...so with time this iteration increases because no. of element in the pw increases.

initially pw contains just " " then 1 then 2 & 12 assume int[] a {1,2} ...so with time this iteration increases because no. of element in the pw increases.

The Only way to learn is ...........do!

Visit my blog http://inaved-momin.blogspot.com/

Mike Simmons

Ranch Hand

Posts: 3028

10

posted 3 years ago

OK, so it increases with the number of elements, true. But so does O(n^2) or O(log(n)) or an infinite number of other functions. Do you have any reason to believe this is O(n) as opposed to one of those others?

Here's another way to look at it. If you have n elements in a set, is there a formula for number of elements in the powerset? Is there any way an algorithm to list all the elements could be faster than O(number_in_powerset)?

naved momin wrote:This iteration increases as the no. of element in pw increases for eg:

initially pw contains just " " then 1 then 2 & 12 assume int[] a {1,2} ...so with time this iteration increases because no. of element in the pw increases.

OK, so it increases with the number of elements, true. But so does O(n^2) or O(log(n)) or an infinite number of other functions. Do you have any reason to believe this is O(n) as opposed to one of those others?

Here's another way to look at it. If you have n elements in a set, is there a formula for number of elements in the powerset? Is there any way an algorithm to list all the elements could be faster than O(number_in_powerset)?

posted 3 years ago

ya the formula is n^2 ..suppose i have 2 element in set than in power set there will be 2^2 = 4 elements

i guess its an exponential function (c^n where c > 1) what you think?

i guess its an exponential function (c^n where c > 1) what you think?

The Only way to learn is ...........do!

Visit my blog http://inaved-momin.blogspot.com/

Mike Simmons

Ranch Hand

Posts: 3028

10

posted 3 years ago

I think you need to be more specific what you're talking about. First "the formula" is n^2... then you guess "it" is an exponential function. Are you talking about the same formula? Formula for what, exactly?

OK, good start. What if there are 3 elements? How many elements would be in the powerset? Is it 3^2, 2^3, or something else? And what if there are 4 elements?

naved momin wrote:suppose i have 2 element in set than in power set there will be 2^2 = 4 elements

OK, good start. What if there are 3 elements? How many elements would be in the powerset? Is it 3^2, 2^3, or something else? And what if there are 4 elements?

posted 3 years ago

ok. my mistake , i thought you are aware about powerset ...but not a problem lets take a quick session on powerset , it is denoted as p(s) e.g: let s be a set {1,2,3} & p(s) = {null(written as '{}' ),1,2,3,12,13,23,123}

so i guess till now you know the formula for powerset , yes it is 2^n where n is the no. of elements in set.

so i guess till now you know the formula for powerset , yes it is 2^n where n is the no. of elements in set.

The Only way to learn is ...........do!

Visit my blog http://inaved-momin.blogspot.com/

Mike Simmons

Ranch Hand

Posts: 3028

10

posted 3 years ago

Um, yes, thank you, I am aware of that. I'm trying to get you to focus your thoughts more clearly, though. In your previous post you were talking about a formula being n^2 - did you mean 2^n, or were you talking about something else?

I would suggest that if there are 2^n elements in the powerset, then any algorithm to list them all cannot possibly be any faster than 2^n. It might be slower, but never faster. If your objective is to list them all, then time will be at least O(P), where P is the number of elements in the powerset. Which is 2^n. So, the best possible time you will ever get is O(2^n). This suggests that your original posts talking about O(n^2) are... what's the word? Completely wrong. And I think it's because of this line:

This is

I would suggest that if there are 2^n elements in the powerset, then any algorithm to list them all cannot possibly be any faster than 2^n. It might be slower, but never faster. If your objective is to list them all, then time will be at least O(P), where P is the number of elements in the powerset. Which is 2^n. So, the best possible time you will ever get is O(2^n). This suggests that your original posts talking about O(n^2) are... what's the word? Completely wrong. And I think it's because of this line:

This is

*not*O(n), it's O(num_elements_in_pw), which appears to be O(2^(n-1)), which is O(2^n).