Skip to content

Instantly share code, notes, and snippets.

@parasyte parasyte/README.md
Last active Jul 24, 2019

Embed
What would you like to do?
Various solutions for Nth Fib

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

def fib(n):
"""O(n) time complexity, O(n) space complexity"""
if n < 2:
return n
return fib(n - 2) + fib(n - 1)
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
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))
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.