Executing the Subset sum problem should be fast, right?

I’ve been getting my hands dirty in Data structures and Algorithms using C++, and one of the problems I had to face was the Subset sum problem.

What is the Subset sum Problem?

Essentially, it’s a way to calculate maximize efficiency. Imagine if you had a commute of exactly 1 hour, and your iPod can store only 1 hour, or 3600 seconds of music. You don’t want to listen to the same song right? So, the subset sum problem is a way to compile all the songs you have, and then create a set of songs that will fit into exactly 1 hour of songs.

Calculating this should be easy for a computer… right?

I don’t have the latest and greatest computer, but it sure is fast enough. I have an Early 2015 12,1 Macbook Pro. It’s got a dual core Intel i5 clocked at 2.7GHz, with 8gbs of ram. So this calculation should be fast.

How I’ll test this…

Lets try 300seconds, or 5 minutes worth of songs. Then continue on in 300second increments, or 5 minutes. But the only thing I won’t be doing is exiting out of the code, when we have met our target.

Let’s try it out…


Hmm. 300 seconds took only 0.000498 seconds. Nice. That was fast.


0.014084seconds.. Still pretty fast.


0.737482seconds… not bad at all still..


21.1275seconds? WHAT?

This has to be an error right? Sadly, no.

I tried testing out 1500seconds. It would compile, but it took way too long…


Extime, refers to execution time, while time refers to the amount of space (in time) we have on our iPod.

According to these data points alone, we have an exponential curve, and that makes sense, as every time we try to add a new song to a set and it passes our test, the number of sets will continue to grow. Screen Shot 2017-01-12 at 12.33.42 PM.png


I guess our “advanced” computers aren’t so advanced after all…

Well.. Back to optimizing my program….


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s