Various solutions for Nth Fib

README.md

Given the sequence A000045 and an input parameter n, produce the Nth number in the sequence.

a.py

def fib(n):
    """O(n) time complexity, O(n) space complexity"""
    if n < 2:
        return n

    return fib(n - 2) + fib(n - 1)

b.py

def fib(n):
    """O(n) time complexity, O(1) space complexity"""
    a = 0
    b = 1

    for i in range(n):
        a, b = b, a + b

    return a

c.py

import math

def fib(n):
    """O(1) time complexity, O(1) space complexity"""
    # See: https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression
    phi = (1.0 + math.sqrt(5.0)) / 2.0
    psi = -(1.0 / phi)

    return int((math.pow(phi, n) - math.pow(psi, n)) / (phi - psi))

test.py

import unittest

class TestFib(unittest.TestCase):
    def do_test(self, fn):
        actual = [ fn(n) for n in range(10) ]
        expected = [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ]
        self.assertEqual(actual, expected)

    def test_fib_a(self):
        from a import fib
        self.do_test(fib)

    def test_fib_b(self):
        from b import fib
        self.do_test(fib)

    def test_fib_c(self):
        from c import fib
        self.do_test(fib)

if __name__ == '__main__':
    unittest.main()