2^n complexity algorithm

Question

I need to implement and test an algorithm with a 2^n complexity. I have been trying to find one for a while. If there is any way I can acheive this by implementation -- with a exact complexity of 2^n that would be optimal. If anyone knows of a location I can find an example, or could help me implement one, that would be awesome :-). The basic operation can be anything, but a single statment like i++; would be best.

Solution 1

Generate all subsets of a set with n elements.

Added. The simplest way of generating all the subsets of S = {a0, a1, ..., an-1} is probably to translate between the binary representation of the rank and the subset.

Take S = {a0, a1, a2}.

rank binary subset
0    000    {} 
1    001    {a0}
2    010    {a1}
3    011    {a0, a1}
4    100    {a2}
5    101    {a0, a2}
6    110    {a1, a2}
7    111    {a0, a1, a2}

So, a 1 in the binary means the corresponding element is in the subset. A 0 means the element is not in the subset.

But you should also lookup Gray code.

Solution 2

The classical recursive Fibonacci number calculation is O(2^n).

unsigned Fib(unsigned n)
{
    if (n <= 1)
        return n;
    else
        return Fib(n - 1) + Fib(n - 2);
}

---

Since the above is actually theta(Phi^n), I'm adding a theta(2^n) algorithm that return 2^n. Thanks to Jeremiah Willcock.

unsigned TwoExp(unsigned n)
{
    if (n == 0)
        return 1;
    else
        return TwoExp(n - 1) + TwoExp(n - 1);
}

Solution 3

Quantum Bogosort has 2^n space complexity.

Solution 4

I spent a great deal of time rethinking the problem and would like to post a solution I came up with. All of the answers contributed to my ability to come up with this solution, and am very thankful for everyone that reponded. :-) I realize that algorithm does practically nothing.

it is written in java
can't seem to get the tabs to work
basic operation is i++;

public class TwoToTheN
{  
     private static int twoToTheN = 0;  
     private static int power = 3;

     public static void main(String[] args)   
     {  
         twoToTheN(power);  
         System.out.println(twoToTheN);  
     }  

     private static void twoToTheN(int n)  
     {  
         if(n == 0)   
         {  
             twoToTheN++;  
             return;  
         } 
         else if(n == 1)  
         {  
             twoToTheN++;  
             twoToTheN++;  
             return;  
         }  
         twoToTheN(n-1);  
         twoToTheN(n-1);  
     }
}  

View more solutions

Comments

[Jeremiah Willcock]

Isn't it only O(Fib(n)), which is only about 1.6^n? If you replaced Fib(n - 2) by Fib(n - 1) at the bottom, though, it would become 2^n.

[ThomasMcLeod]

@Jeremiah, yes, technically this algorithm is theta(Phi^n), which is in O(2^n). (Phi = (5^(1/2) + 1) / 2, about 1.61.

[rubixibuc]

Thank you :-) That's perfect, do you know where I can find a sample implementation of this?

[rubixibuc]

or how I can just implement the controls structure and just do i++ for the statement.

[Anycorn]

I'm just gonna vote you up and down to see the unicorns dance.

[Nick Johnson]

Pretty sure it has n! space complexity.