You don’t need to be a math whiz to be a good programmer, but there are a handful of tricks you will want to add to your problem solving bag to improve the performance of your algorithms and make an impression in technical interviews. In this tutorial, you will learn how to sum consecutive powers of 2 with a simple and easy to remember equation. Knowing this equation will help you understand recursive runtimes and quickly calculate Big O time and space complexities.

_This article originally published onjarednielsen.com

How to Sum Consecutive Powers of 2

How would you add these numbers?

2^0 + 2^1 + 2^2 + 2^3

Was your first thought to take the ‘brute force’ approach?

2^0 = 12^1 = 2, + 1 = 32^2 = 4, + 3 = 72^3 = 8, + 7 = 15

Nothing wrong with that and you probably didn’t need a pen and paper or a calculator to get there.

What if the final power was not 2^3 but 2^30? Or 2^300?

Brute force would be brutal.

What if you were presented with this situation?

2^0 + 2^1 + 2^2 + … + 2^n = ?

How would you solve this?

Programming is Problem Solving

What is programming?

Programming is problem solving.

What problems do we solve?

There are two primary categories of problems we solve as programmers:

• Automation
• Algorithms

We could write a for loop to automate the addition of our powers of 2:

constsumPowers2=power=>{letsum=0;for(leti=0;i<power;i++){sum+=2**i;}returnsum;}

Will it scale?

What’s the Big O?

O(n).

Why?

Our function needs to perform one operation for every input, so the order of our algorithm isO(n) or linear time complexity.

There must be a better way!

Rather than automate the brute force approach, how can we solve this problemalgorithmically?

Math O’Clock 🧮 🕐

I’m about to blow your mind.

Check this out:

1 = 1

😐

Bear with me.

🐻

If1 is equal to1, then it follows that

1 = 2 - 1

And if

1 + 2 = 3

Then it follows that

1 + 2 = 4 - 1

Let’s take it one more step. If

1 + 2 + 4 = 7

Then

1 + 2 + 4 = 8 - 1

Cool?

😎

Let’s power up!

What isx in this equation?

2^x = 8

Or, in plain English, “How many 2s multiplied together does it take to get 8?”

We could also write it as a logarithm:

log2(8) = 3

We could say, “To what power do we raise 2 for a product of 8?”

🧐

We know that2^2 = 4.

And2^1 = 2

And2^0 = 1.

“Wait, what?”

Why is2^0 = 1?

Table time! 🏓

See the pattern?

What is2^4?

16

What is the sum of the powers of2^4?

1 + 2 + 4 + 8 + 16 = 31

What’s another way we can describe31?

31 = 32 - 1

What is2^5?

32

Did you see what happened there?

The sum of the powers of two is one less than the product of the next power.

🤯

Let’s make another table! 🏓🏓

What’s the next exponent?

2^6

What’s2^6?

64

So what is the sum of the powers of2^6?

🤔

Let’s convert this pattern to an equation to find out.

What if our exponent is unknown, orn?

2^n

What is the sum of2^n?

☝️ The sum of the powers of two is one less than the product of the next power.

If our power isn, what’s the next power?

n + 1

Ifn is equal to1, then it follows

2^n = 22^(n + 1) = 4

And ifn is equal to2, then it follows

2^n = 42^(n + 1) = 8

Lookin’ good!

How do we getone less than the product of the next power?

We simply subtract1:

2^(n + 1) - 1

🎉 There's our equation!

Programming is Problem Solving

Let’s take another look at our function from above. How can we refactor this to improve its time complexity?

constsumPowers2=power=>{letsum=0;for(leti=0;i<power;i++){sum+=2**i;}returnsum;}

We simply translate our equation into JavaScript!

constsumPowers2=power=>2**(power+1)-1;

What’s the order of our new function?

O(1).

Regardless of the size of the input, our function will always perform the same number of operations.

How to Sum Consecutive Powers of 2

You don’t need to be a math whiz to be a good programmer, but there are a handful of equations you will want to add to your problem solving toolbox. In this tutorial, you learned how to sum consecutive powers of 2 with a simple and easy to remember equation. Knowing this equation will help you understand recursive runtimes and quickly calculate Big O time and space complexities.

Want to level up your problem solving skills? I write a weekly newsletter about programming, problem solving and lifelong learning.

Sign up for The Solution