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) 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 =='red' ? true : false end
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) 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) 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 ;)