CODEWITHSUNDEEP
algorithm
jcm
jcm

Reputation: 5659

What does this explanation of Big O(2^n) mean?

I was reading about Big Oh notation in Skiena's Algorithm Design Manual and came across the following explanation of O(2n):

Exponential functions: Functions like 2n arise when enumerating all subsets of n items.

What does this mean in terms of a concrete example?

Say I have the set: {1,2,3,4} (therefore n=4), this would mean (according to Skiena's definition) that the number of subsets is 24 which is 16 subsets. I can't figure out what these 16 subsets are.

Does the 2 in the relation 2n mean that the subsets are restricted to a size of 2 each?

Edit: I guess part of what I'm asking is, why 2n and not 3n for example? This doesn't feel intuitive at all to me.

Upvotes: 0

Views: 182

Answers (2)

paxdiablo
paxdiablo

Reputation: 882146

  • One subset of 0 elements: {}
  • Four subsets of 1 element: {1} {2} {3} {4}
  • Six subsets of 2 elements: {1,2} {1,3} {1,4} {2,3} {2,4} {3,4}
  • Four subsets of 3 elements: {1,2,3} {1,2,4} {1,3,4} {2,3,4}
  • One subset of 4 elements {1,2,3,4}

Totals subsets is therefore sixteen.

The 2 in the 2n simply means that the "workload" rises in proportion to the exponential function of n. This is much worse than even n2 where it simply rises with the square.

This set of all sets of a finite set is known as a power set and, if you really want to know why it's 2n, the properties section of that page explains:

We write any subset of S in the format {X1, X2, ..., Xn} where Xi,1<=i<=n, can take the value of 0 or 1. If Xi = 1, the i-th element of S is in the subset; otherwise, the i-th element is not in the subset. Clearly the number of distinct subsets that can be constructed this way is 2n.

Basically what that means in layman's terms is that, in a given subset, each element can either be there or not there. The number of possibilities is therefore similar to what you see with n-bit binary numbers.

For one bit, there are two possibilities 0/1, equivalent to the set {a} which has subsets {} {a}.

For two bits, four possibilities 00/01/10/11, equivalent to the set {a,b} which has subsets {} {a} {b} {a,b}.

For three bits, eight possibilities 000/001/010/011/100/101/110/111, equivalent to the set {a,b,c} which has subsets {} {a} {b} {c} {a,b} {a,c} {b,c} {a,b,c}.

And so on, including the next step of four elements giving sixteen possibilities as already seen above.

Upvotes: 1

Chris Taylor
Chris Taylor

Reputation: 47402

Here's a list of the all valid subsets of {1, 2, 3, 4}:

{}                                           1

{1}, {2}, {3}, {4}                        +  4

{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}  +  6

{1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}        +  4

{1,2,3,4}                                 +  1

                                          = 16

The reason that the count is 2ⁿ and not 3ⁿ is that to create a subset, you can imagine going through each element and making the decision "is the element in the subset or not?".

That is, you choose between two possibilities (in and out) for each of n elements, so the total number of ways to make this decision (and thus the total number of subsets) is

    2 * 2 * 2 * .... * 2
    \________  ________/
             \/
           n times

which is 2ⁿ.

Upvotes: 5

Related Questions