# 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.