Order 2^N - Exponential

O(2^n) is the first Big O class that we've dealt with that falls into the scary exponential category of algorithms.

Algorithms that grow at an exponential rate become impossible to compute after so few iterations that they are almost worthless in practicality.

Assignment

At LockedIn, we need to be able to compute the power set of a set of influencers. It has something to do with targeting segments of an audience with ads. I don't know, I just work here.

A power set consists of all possible subsets (combinations) of elements in a given collection, include an empty subset and the original set itself. For example, the power set of [1, 2, 3] is:

[
  [], # empty subset
  [1],
  [2],
  [3],
  [1, 2],
  [1, 3],
  [2, 3],
  [1, 2, 3], # original set
]

Complete the power_set function using the following algorithm. It takes a list of numbers and returns a list of lists of numbers.

If the input list is empty, return the powerset of an empty set (a list containing an empty list)
Otherwise, create a list named all_subsets. This will hold the result.
Ensure all_subsets contains an empty list to start. You will not do anything else with this empty list.
For each element in the input list:
1. Create an empty list named new_subsets.
2. For each subset in all_subsets:
  1. Add the current element to the existing subset to create a new subset.
  2. Append the new_subset to new_subsets.
3. After the inner loop, use extend to add new_subsets to all_subsets

Observe!

Notice the growth rate of a power set is 2^n, where the number of elements in the original set is the exponent n. Each new element in the input doubles the size of the power set! Therefore, its complexity class is O(2^n).

If we could calculate one subset per millisecond, completing the power_set() of just 25 items would take approximately 9 hours, and that's not accounting for the massive amounts of memory we would need. 40 items would take over 34 years!