Big O Notation: O(2^N)

#algorithms #bigo #beginners

Song of the Week

This week we're gonna take a look at O(2^N). This runtime complexity can be found in recursive functions.

Tower of Hanoi

Let's take a look at an example in which recursion is used to print out the moves required to solve the Tower of Hanoi puzzle. If you're unfamiliar, the Tower of Hanoi is a game in which you have a stack of disk on one peg that decrease in size as you go up that stack. The goal is to move all the disks to one of the other two pegs by only moving one disk at a time and you can't put a disk on top of a smaller disk. In the following diagram we can see the steps needed to solve the puzzle when there are only three disks in the tower.

Now that we understand the problem, let's take a look at the recursive solution in JavaScript.

const towerOfHanoi = (n, from_rod, to_rod, aux_rod) => { 
  if (n == 1) { 
    console.log("Move disk 1 from rod " +  from_rod + " to rod " + to_rod); 
    return; 
  } 
  towerOfHanoi(n-1, from_rod, aux_rod, to_rod); 
  console.log("Move disk " + n + " from rod " +  from_rod + " to rod " + to_rod); 
  towerOfHanoi(n-1, aux_rod, to_rod, from_rod); 
}

How this function works is pretty interesting, but I'm not going to cover it here since were focused on Big O complexity of this function. To read more on how it works, click one of links under references.

To determine the Big O runtime complexity we need to look at how many recursive calls are made. In this case there are two, and each of those recursive calls passes in n-1 as the new number disks. So a each call to the function doubles the number of recursive calls until n-1 is equal to 1.

If N was equal to 4,
N=4 -> 1 function call
N=3 -> 2 * previous function calls = 1 * 2 = 2
N=2 -> 2 * previous function calls = 2 * 2¹ = 2²
N=1 -> 2 * previous function calls = 2 * 2² = 2³

The more general expression of the trend we see would be,
2⁰ + 2¹ + 2² + 2³ + 2^N-1 =
2^N - 1
Since constants drop off when expressing the Big O complexity, the runtime complexity of the Tower of Hanoi is O(2^N).

The Pattern

The pattern to watch for is that if a recursive function makes more then one call, the complexity is often O(branches^depth), where branches refers the number recursive calls made and the depth refers to the depth of the tree this creates.

Also keep in mind that even though constants are usually dropped when expression Big O complexity, the base of an exponent does matter. So, O(2^N) is very different from O(8^N).

Conclusion

O(2^N) runtime complexities are often seen in recursive functions that make 2 recursive calls and pass in the problem size of N-1.
If a recursive function makes more then one call, the complex is often O(branches^depth)
The base of an exponent does matter. O(2^N) is very different from O(8^N)