Ruby Computer Science - Big O Algorithms

Question Click to View Answer

What is Big O notation?

Big O is used to represent how long it will take to run a function based on different inputs. Big O notation is not meant to be precise. We want to know if the run time is constant, linear, exponential, or logarithmic and usually don't care about specific details like the slope of a linear graph or the y-intercept. Big O assumes the worst case input (i.e. Big O assumes that the input is the input that will cause the function to run the slowest).

What is the Big O notation for the following function (don't need to formally define the Big O notation, just say if it is linear, logarithmic, etc.)?

def present?(array, element)
  array.each do |e|
    return true if e == element
  end
  false
end

linear

The running time of the present? function depends on how long the input array is. Big O assumes the worst-case scenario and present?([1, :a, :b, :dog], 2) is a worst-case example for this method because every element of the array is iterated over. If the array gets 10 times longer, the present? method will take 10 times longer to run because there are more elements to iterate over.

Explain what the following code returns?

require 'benchmark'

result = Benchmark.measure do
  x = 5
  10_000_000.times do
    x += 1
  end
end

p result

This code returns 4 numbers that vary based on the computing power of your machine. Here are the numbers on my computer: 0.800000 0.000000 0.800000 ( 0.805508)

The first number is the user time, the second number is the system time, and the last number is the total time. We will focus on the total time in this quiz.

How much greater will the total runtime be for million_items than ten_million_items?

require 'benchmark'

def present?(array, element)
  array.each do |e|
    return true if e == element
  end
  false
end

million_items = Benchmark.measure do
  present?((1..1_000_000).to_a, :bob)
end

ten_million_items = Benchmark.measure do
  present?((1..10_000_000).to_a, :bob)
end

The total runtime for ten_million_items will be 10 times greater than the total runtime for million_items because the complexity of the present? function is linear and the ten_million_items array is 10 times larger than the million_items array. On my machine, million_items takes 0.22 seconds to run and ten_million_items takes 2.28 seconds to run.

Describe the Big O complexity of the following function:

def combine(a, b)
  result = []
  a.each do |i|
    b.each do |j|
      result << [i, j]
    end
  end
  result
end

exponential

As the arrays a and b get larger, the computation time will increase exponentially. The following benchmarking demonstrates the exponential increase in computation time:

first = Benchmark.measure do
  combine((1..2_000).to_a, (1..2_000).to_a)
end

second = Benchmark.measure do
  combine((1..4_000).to_a, (1..4_000).to_a)
end

On my machine, the total computation time for first is 0.85 seconds and the total time for second is 2.83 seconds. The array sizes doubled in second, but the computation time increased 3.33 times, thus indicating an exponential relationship.

Describe the Big O complexity of the following function:

def multiply_by_two(x)
  x * 2
end

constant

As the input to the multiply_by_two method gets larger or smaller, the computation time does not change. The first and second variables in the following example have a total run time of 0.0000 on my machine as this simple method can be run almost instantaneously, regardless of input size.

first = Benchmark.measure do
  multiply_by_two(10)
end

second = Benchmark.measure do
  multiply_by_two(10_000_000_000_000_000)
end

Describe the Big O complexity of the following function as the array size grows:

def my_index(array, value)
  low = 0
  high = array.length - 1
  while low <= high
    mid = (low + high) / 2
    if array[mid] > value
      high = mid - 1
    elsif array[mid] < value
      low = mid + 1
    else
      return mid
    end
  end
  nil
end

log

The my_index method implements the binary search algorithm that works on sorted arrays. For every iteration, half the results are eliminated from consideration, which makes this a fast algorithm. For a sorted array, it is much faster to do a binary search than iterate over every element in the array.