Big O – w/ Ruby Examples

I had a hard time finding an explanation of all basic Big O concepts with practical use cases and code examples (ruby).

Each algorithm is broken down into 4 parts:
  1. Basic Definition (only what you need to know to understand the basics of this approach).
  2. Real life example (what you do in your daily life that mirrors this algorithm, reading a book, feeding your cat etc).
  3. Ruby code example (the most basic code example that I can think of).
  4. Other things you have done or may do in your programming day to day.

O(n) – Linear Complexity

What you need to know:

Takes a linear amount of time based on the size of the data set (n). If there is twice as much data it will take twice the amount of time. You generally do not want to use this for large data sets, the linear approach is very slow.

Real Life Example:

It will always take you foo minutes to read a book that is bar pages long.

Ruby code examples are worth 10k words:

Iterating through an array one at a time from beginning to end

hair_products = ["shampoo", "conditioner", "hair dryer"]

hair_products.each {|item| puts item}

=> shampoo
=> conditioner
=> hair dryer

There are many other practical code examples for O(n):

1. Linear Search
2. Determining if a string is a Palindrome (very practical :).

O(log n)

What you need to know:

Definitely a smarter way to search than the linear O(n) if you’re working with a large data set. This is binary search (divide and conquer). All this means, in the simplest form, is you start in the middle, then you start in the middle again, and again until you find/reach desired goal.

Cautionary Tail About Binary Search

Jon Bentley, in his book Programming Pearls, reports that 90% of professional programmers cannot write a proper implementation of binary search in two hours, and Donald Knuth, in the second volume of his book The Art of Computer Programming, reports that though the first binary search was published in 1946, the first bug-free binary search wasn’t published until 1962.

Ruby code examples are worth 10k words:

For this example we’re going to use a very large array of numbers. Let’s assume we’re looking for number 46, but we don’t know where it is located so we can’t access it by it’s index. If we used linear search, O(n) we would just loop through each element in the array and compare it to the num until we found a match. If this array was large this would take a very long time. Enter binary search, O(log n).

def binary_search(num, array)
  lower = array.index(array.first)
  higher = array.index(array.last)

  while lower <= higher do
    middle = (lower + higher) / 2
    return middle if array[middle] == num
    return -1 if lower == higher

    if num < array[middle]       higher = middle - 1     elsif num > array[middle]
      lower = middle + 1

test_array = (100..200).to_a
binary_search(46, test_array)

Okay, I am spent….
I am stopping for the night but will cover the the follow later: chow!

O(n log n)


Leave a Reply