Algorithms and Time Complexity: Making Code Efficient

Login to Access Code

“Algorithm.”

As I say the word I can feel my brain getting emptier…as if the word is a forget-me-when-you-hear-me spell. Thinking about it makes me dizzy.

What does it MEAN?

At its most basic, an algorithm is just a set of step-by-step instructions for carrying out a specific task. From your washing machine to the most secure networks in the world, algorithms help us do things well. Need to find the shortest distance between two points? Give Dijkstra’s algorithm a shot. Amazed by Google’s ability to find that perfect webpage for your search? They use PageRank. Surprised no one has managed to steal everyone’s personal data (though people certainly are trying!)? You can thank SHA-1.

Ok, I hear you…big deal right? Algorithms do things. But how? What gives them these powers? Let’s check back in with our washing machine.

To wash clothes, the washer machine doesn’t have a single ‘wash’ step that magically does everything (though that would be pretty cool). Instead, the engineer that made that washing machine had to think, “Hmm…if I want to wash something, what exactly does that mean? What are the steps that make up 'washing’? How do I build something that can implement all these steps in the best order?” In short, the washing machine engineer needs to come up with a washing algorithm. Let’s sketch out a superficial version of that algorithm.

We know we need to accomplish a few things to ‘wash’ clothes:

  1. We need water
  2. We need soap
  3. We need agitation
  4. The clothes need to be rinsed
  5. Our machine needs to be able to combine all these features

Understanding that we can break the mega-task “wash” into at least 4 smaller actions is a crucial step in understanding algorithms. As programmers, it is our job to tinker with these steps, and find not just any way to code out the steps, but the best way.

Washer Maybe nothing is simple when you break it down. Thanks to Google for the image.

In this article, we will discuss:

  • Modeling and Pseudocode
  • Good or bad? Fast or slow.
  • Big O and time complexity
  • Problem solving: Euler No.1

Understanding the Challenge

One of my biggest struggles with coding, or more generally ‘logic’, is that I have trouble “zooming in.” When I am told “We need X to do Y,” I tend to not have a clear vision down the road towards 'Solution Land.’ Thankfully, I have a few steps that help guide me towards those sweet, solution-rich thoughts.

Analyze the problem

Much like our washing machine problem, making X do Y is often not as straightforward as “make ‘variable’ print”. We need to understand more about what has been given to us. What is Y? How is it related to X, if at all? What type of information does X contain? Does that give us better options for getting it to do Y?

Once the structure of the challenge is clear, write pseudocode to further illuminate each step of the process. Search for edgecases and other aspects of your code that can be potential problems. Make sure, at least to get started, that your goal has been broken down into smaller steps.

“Just Works” Solution

Think of the just-works solution as the Pseudocode Caterpillar. It’s definitely alive, but not quite the Code Butterfly we hope to show off to all our friends. This version of your solution is the rough draft that helps clarify what is left to be tackled, while ensuring no major aspect of the code has been overlooked.

Pseudopillar Such a cute pseudopillar.

The takeaway so far is this: challenges in programming can and should be broken down into manageable coding tasks, and before worrying about the 'perfect’ solution to a challenge, make sure you have a just-works solution that addresses the algorithm’s core functionality requirements.

Good Algorithms are Fast Algorithms

In my last article, we looked at how even small differences in our algorithms can turn them from omnipotent language machines to just…useless. One algorithm gave us results in less than a second, while the other might have been in the order of days or weeks.

You might be wondering, “Is there a good way to know how quickly my algorithm will run?”

Yes, there certainly is! In fact, we are going to look at two tools. One we jimmied from our friends in the Math department, and the other is a gift from the Ruby gods.

The first tool we will discuss is Big O notation. Rob Bell wrote an excellent article that can cover the details with a finer comb than we will here, but to put it succinctly, Big O represents an algorithm’s computing time as it relates to the size of its input data. This relationship, computing time v. input size, is referred to as time complexity (the ‘O’ in Big O is short for ‘Order’, as in 'order of growth’).

So, Big O is a way to calculate and represent the time complexity of our algorithms.

The second tool is a gift, and it is a gift called Benchmark. The Benchmark module let’s us see four processing-time values for our algorithm. It will show us the user CPU time, system CPU time, the sum of user and system CPU times, and the elapsed ‘real’ time (in that order). Let’s see how this module works on last week’s fast Fibonacci method:

require 'benchmark'

puts Benchmark.measure {
  @fib_hash = {}
  def best_fib(n) 
    @fib_hash[n] =                                                                    
      if n <= 1                                                                       
        n                                                                             
      else 
    @fib_hash[n] ||= best_fib(n-1) + best_fib(n-2)                                
      end                                                                              
  end 
best_fib(1000)
}

#=> 0.000000    0.000000    0.000000    (    0.000756)

It is important to notice that because Benchmark is a Ruby module, we need to require it on any doc that calls it. And while there are certainly a lot of ways to use the Benchmark module (.measure is just one of its methods), the above way is simple and illustrative.

By the way, that Fibonacci sequence is O(2^n). Can you calculate that value on your own?

Let’s look at a new problem together.

Euler No.1

Project Euler is a great site for testing your logic and programming skills. Hundreds of thousands of people have attempted and solved a lot of these problems. Let’s join their ranks and look at Euler Problem No.1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Take a moment and see if you can do this on your own. When I first attempted the problem, I got hung up thinking about a mathematical solution (because so many numbers, right?), so I encourage you to instead focus on using your fundamental Ruby skills to approach this problem.

Analyze the Problem

What exactly are we being asked? We need to move through each number between 0 and 999 (values below 1000) and find every number that is divisible by 3 or 5 (if it is divisible by x, then it is a multiple of x). When we find a match to our condition, that match needs to be added to a running total.

Pseudocode the Problem

In our analysis above, we did a good job of using plain English to describe a solution. The next step is to translate that same 'plain English’ using Ruby methods and concepts:

  • Iterate over the range (0..999)
  • For each value that is either divisible by 3 or divisible by 5, add it to our sum

This pseudocode looks more like code than our initial analysis, and tries to take advantage of key Ruby words like iterate and range and each.

Just-Works Solution

counter = 0
(0...1000).each do |i| 
    counter += i if i % 3 == 0 || i % 5 == 0 
end

puts counter

#=> 233168

After a little refactoring:

counter = 0
(3..999).each { |i| counter += i if i % 3 == 0 || i % 5 == 0 }

puts counter

#=> 233168

We set a counter variable and then iterate over 3 to 999 (3 is the lowest value that meets our condition, so it seemed like a good starting point). Add each integer i to our counter if i modulo 3 or 5 equals 0, which is to say that the remainder when i is divided by 3 or 5 will be equal to 0 .

This gives us our solution, 233168.

To me, this algorithm really illustrates how close to human language Ruby can feel sometimes.

Using the Benchmark module

The format is simple, pass your code block inside: Benchmark.measure { [code block] }.

require ‘benchmark’

puts Benchmark.measure {
  counter = 0
  (0...1000).each { |i| counter += i if i % 3 == 0 || i % 5 == 0 } 
 }

#=> 0.000000     0.000000     0.000000     0.000096

At O(N), and a real processing time of .000096 seconds, I’d say this iteration of our algorithm does a pretty good job of satisfying our solution.

Summary

We rely on algorithms to be fast and achieve the correct solution. To write an algorithm well, we first need to analyze the problem and make sure we understand how our task breaks down into smaller restraints. We then work on transitioning from this analysis into a just-works solution. In programming, we typically need algorithms to function optimally with even very large input. We can check how our algorithms will perform at scale with Big O (Order of growth) notation, a way of representing an algorithm’s time complexity. We refactor our algorithm until we achieve the desired time complexity. We can find accurate run-time data by using the Benchmark module.