"""
CS 101 Timing alternative ways to compute Fibonacci sequence
"""

import random
import time

def fib_exponential(n):
    """
    Return nth Fibonacci number.
    This implementation is very inefficient!
    Runs in O(2^n) time!
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib_exponential(n-2) + fib_exponential(n-1)
    
def fib_linear(n):
    """
    Return nth Fibonacci number.
    Uses iterative strategy, implemented with tail recursion
    Runs in O(n) time
    """
    return 0

def fib_exponential_test(n):
    """
    Computes the nth Fibonacci number and times the computation
    using the naive exponential-time version.
    """
        
    begin = time.time()   
    f = fib_exponential(n)
    elapsed = time.time() - begin
    return (f, elapsed)

def fib_linear_test(n):
    """
    Computes the nth Fibonacci number and times the computation
    using the tail-recursive linear-time version.
    """
        
    begin = time.time()   
    f = fib_linear(n)
    elapsed = time.time() - begin
    return (f, elapsed)