Example of Big O of 2^n

Question

So I can picture what an algorithm is that has a complexity of n^c, just the number of nested for loops.

for (var i = 0; i < dataset.len; i++ {     for (var j = 0; j < dataset.len; j++) {         //do stuff with i and j     } } 

Log is something that splits the data set in half every time, binary search does this (not entirely sure what code for this looks like).

But what is a simple example of an algorithm that is c^n or more specifically 2^n. Is O(2^n) based on loops through data? Or how data is split? Or something else entirely?

Answer 1

Algorithms with running time O(2^N) are often recursive algorithms that solve a problem of size N by recursively solving two smaller problems of size N-1.

This program, for instance prints out all the moves necessary to solve the famous "Towers of Hanoi" problem for N disks in pseudo-code

void solve_hanoi(int N, string from_peg, string to_peg, string spare_peg) {     if (N<1) {         return;     }     if (N>1) {         solve_hanoi(N-1, from_peg, spare_peg, to_peg);     }     print "move from " + from_peg + " to " + to_peg;     if (N>1) {         solve_hanoi(N-1, spare_peg, to_peg, from_peg);     } } 

Let T(N) be the time it takes for N disks.

We have:

T(1) = O(1) and T(N) = O(1) + 2*T(N-1) when N>1 

If you repeatedly expand the last term, you get:

T(N) = 3*O(1) + 4*T(N-2) T(N) = 7*O(1) + 8*T(N-3) ... T(N) = (2^(N-1)-1)*O(1) + (2^(N-1))*T(1) T(N) = (2^N - 1)*O(1) T(N) = O(2^N) 

To actually figure this out, you just have to know that certain patterns in the recurrence relation lead to exponential results. Generally T(N) = ... + C*T(N-1) with C > 1means O(x^N). See:

https://en.wikipedia.org/wiki/Recurrence_relation