Big O Notation

Big O Notation was one those concepts that always seemed to escape me. Sure I could, if asked in an interview respond with the overtly simple “Big O Notation is a metric to measure an algorithm performance”. Ask me to explain any further and I would be in a world of confusion and disarray! But after reading multiple blog posts and doing some homework I finally have a grasp of the concept. So here is my attempt to explain it to you!

What is it anyway and why does it matter to me?

Big O Notation is a metric to measure an algorithms performance by how they respond to changes in input size. Sure you can assume that a loop through an array of ten items will be faster than with an array of ten thousand items but how much faster and why? Well Big O Notation helps to explain just that. The bigger and more complex your application grows the more performance starts to become important and understanding the Big O Notation of it’s algorithm can make a world of difference. So lets get into it!

O(1)

O(1) is quite simple. It simply means that the theoretical speed will remain constant and not be dependent on the size of the data structure.

  hash = { name: "DHH", job: "Basecamp", }
  hash[:name]

The hash could have a thousand items or ten thousand items in it and the theoretical speed will remain constant. This is the fastest of the different Big O Notations.

O(n)

O(n) mean the algorithm will increase linearly depending on the size of the data structure. O(n) algorithms typically involve a simple loop through a data structure ie:

  numbers = (1..100)
  numbers.each do |x|
    x.odd? ? (puts "Odd" ) : (puts "Even")
  end

O(n^2)

O(n^2) is most commonly found when dealing with nested loops. For every iteration in the first loop their is an entire iteration through the array. It’s easy to see why nested loops should be avoided.

  numbers = (1..100)
  numbers.each do |x|
    numbers.each do |y|
      p x, y
    end
  end

That’s just a small taste of the most common Big O Notations you will run into. If you wish to expand your knowledge of the subject I recommend taking a look at the Big O Notation Cheat Sheet . Well that’s all from me folk! Like the great Avdi Grimm says “Happy Hacking!”