algorithms

gistfile1.txt

def time_it(&block)
  before = Time.now
  block.call()
  Time.now - before
end

def display_time(&block)
  puts "time took: #{time_it(&block)} seconds"
end


# linear time - O(n)
display_time {
  n = 1000000
  sum = 0
  n.times { |i|
    sum += i
  }
  puts sum
}

# constant time - O(1)
display_time {
  n = 1000000
  puts n * (n - 1) / 2
}

# O(n^2)
# O(log n)
# O(1)

display_time {
  # O(n)
  n = 10000000
  @numbers = n.times.map { rand(100) }
}

def binary_search(array, value)
  return false if array.empty?
  middle_index = array.length/2
  middle_value = array[middle_index]
  if middle_value == value
    true
  elsif middle_value > value
    binary_search(array[0...middle_index], value)
  else
    binary_search(array[(middle_index+1)..-1], value)
  end
end

# worst case
# value is not in the array...
# how long will this algorithim take?

# array.length = 1024
# 1) 1024
# 2) 512
# 3) 256
# 4) 128
# 5) 64
# 6) 32
# 7) 16
# 8) 8
# 9) 4
# 10) 2
# 11) 1
# 12) 0
#       => false

display_time {
  # O(log2 n)
  puts binary_search(@numbers, 20000)
}