Big O Notation & Complexity in Ruby

Tenth and last article in the Prepare for a Ruby job interview series. In this one, we’ll take a look at the Big O Notation and what is Algorithm Complexity.

Big O Notation and Complexity

Big O Notation tells you how complex is an algorithm depending on what you feed it. The important thing to understand with the Big O notation is that it only cares about the worst case scenario.

Here are a few examples of different complexities.

O(1)

O(1) means that the execution time of an algorithm is constant. You can pass 1 item or 1 million items, it will still take the same time to run.

def first_element_is_red?(array)
  array[0] =='red' ? true : false
end

O(n)

O(n) means that the execution time of an algorithm will grow linearly depending on the input size.

def contains?(array, value)
  array.each do |item| 
    return true if item == value
  end
  false
end

Remember when I said the Big O only cares about the worst case ? In this example, we could find the value in the first iteration… or not find it at all, which would be the worst case. That’s why this algorithm has a complexity of O(n).

O(n^2)

O(n^2) means that for each increment of the input size, the speed of the algorithm will double.

If you want an example of this, we can simply write an algorithm that looks for duplicates in an array. Note the nested loop that increase the execution time since for each element, we have to loop through the whole list.

def duplicates?(array1)
  array1.each_with_index do |item1, index1|
    array1.each_with_index do |item2, index2|
      next if index1 == index2
      return true if item1 == item2
    end
  end
  false
end

O(log n)

O(log n) is harder to explain. If I was to show you a graph, we would have a quick growth at the beginning, that tends to get slower in time if you increase the size of the input.

A good example is the Binary Search Algorithm.

def binary_search(array, value, from=0, to=nil)
    to = array.count - 1 unless to
    mid = (from + to) / 2

    if value < array[mid]
        return binary_search(array, value, from, mid - 1)
    elsif value > array[mid]
        return binary_search(array, value, mid + 1, to)
    else
        return mid
    end
end 

p binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16], 15)

I recommend reading more about Big O notation and algorithm complexity, those were just a few examples to get you started ;)

I hope you enjoyed this series of articles. Don’t hesitate to check my Jutsus if you want to learn more about some specific gems ;)