fibonacci

fibonacci.rb

require 'benchmark'

# O(2^n) - exponential
def exp_fib(c = 0)
  return 1 if c < 2
  return exp_fib(c-1) + exp_fib(c-2)
end

# O(n) - linear
def lin_fib(s = 0)
  c = 0
  n = 1

  s.times do |i|
    t = c 
    c = n
    n = t + n
  end

  return c 
end

test_count = 30

lin_test = Benchmark.measure do
  test_count.times do |i|
    lin_fib(i)
  end
end

exp_test = Benchmark.measure do
  test_count.times do |i|
    exp_fib(i)
  end
end
puts "lin_fib(#{lin_test.total}) vs exp_fib(#{exp_test.total})"

# lin_fib(0.0) vs exp_fib(0.32)

# Conclusion : Recursive call is not a solution.