Performance of dynamic Fibonacci generator and dead rabbits I would like to improve my code style and its efficiency. 

I'm just moving beyond the standard recursive approach to a lot of simple algorithms. 

This post has two code snippets with slightly different but related problems. They're both in Python.



The first snippet is just to produce Fibonacci numbers. I think I've done this with O(n) time complexity. Do you have suggestions on how to make my code more readable and more efficient?

# Using bottom-up dynamic programming approach, define all fibonacci numbers
def fib(num):

    # First and second generations are trivial
    if num == 1 or num == 2:
        return 1

    # If not trivial, keep going:

    # Set up array
    allGenerations = [None] * (num + 1)
    allGenerations[1] = 1
    allGenerations[2] = 1

    # Fill in the array until you reach the given generation
    for i in range(3, num+1):
        allGenerations[i] = allGenerations[i - 1] + allGenerations[i - 2]
    return allGenerations[num]




The second snippet tries to use what I learned from the first snippet to solve a related problem. The numbers represent living rabbits. If rabbits lived forever, their population sizes would follow a fibonacci sequence. In this alteration, rabbits live for a fixed amount of time (input m). Newborn rabbits keep living, adult rabbits produce themselves and one offspring, and rabbits that are about to die just produce one offspring (see http://rosalind.info/problems/fibd/).

I'm not sure how to analyze the time complexity of this problem, but it seems high? So questions are (1) What is the time complexity of my solution? and (2) How can I improve efficiency and readability?

def rabbit(n, m):
    # First two generations are trivial
    if n == 1 or n == 2:
        return 1

    # If not trivial, keep going:

    # Set up array
    allGenerations = [None] * (n + 1)

    # Each index in the generations will be another array whose indicies represent the ages of the rabbits in that generation
    allGenerations[1] = [1]
    allGenerations[2] = [0, 1]

    # Bottom-up filling of generations
    for i in range(3, n + 1):
        # Initalize answer as a list of number of rabbits at each age
        answer = [None] * (i)

        # Get the previous generation
        previous = allGenerations[i - 1]

        # Initalize the number of newborns
        newborns = 0

        # From age 1 (first reproductive age) to either age at death 
        # or the oldest in the previous generation (whichever comes first), produce newborn rabbits
        for j in range(1, min(m, len(previous))):
            newborns += previous[j]

        # The 0-index of the answer represents newborn rabbits
        answer[0] = newborns

        # Move every element in the previous generation up one index into the new generation  
        for k in range(0, len(previous)):
            answer[k + 1] = previous[k]

        # Put this answer into the list of all answers
        allGenerations[i] = answer

    # Return all living rabbits
    return sum(answer[:m])

# Some testcases

import unittest

class mainTest(unittest.TestCase):
    def test(self):
        self.assertEqual(rabbit(1, 3), 1)
        self.assertEqual(rabbit(2, 3), 1)
        self.assertEqual(rabbit(3, 3), 2)
        self.assertEqual(rabbit(4, 3), 2)
        self.assertEqual(rabbit(5, 3), 3)
        self.assertEqual(rabbit(6, 3), 4)
        self.assertEqual(rabbit(7, 3), 5)
        self.assertEqual(rabbit(25, 31), 75025)
        self.assertEqual(rabbit(30, 30), 832040)
        self.assertEqual(rabbit(35, 29), 9227437)
        self.assertEqual(rabbit(40, 28), 102333267)
        self.assertEqual(rabbit(45, 27), 1134880302)

if __name__ == '__main__':
    unittest.main(argv=[''], exit = False)
With regard to your time complexity:

With your calculation of the nth Fibonacci number, you could do it in \$O(1)\$ time by using the relation:

$$F_n = \left\lfloor \frac{\varphi^n}{\sqrt{5}} + \frac{1}{2} \right\rfloor$$

So the 484th Fibonacci number would be equal to:

$$\left\lfloor \frac{\varphi^{484}}{\sqrt{5}} + \frac{1}{2} \right\rfloor \approx 6.317 \times 10^{100}$$

If you do not want to use the floor function, you can achieve the exact same result by manipulating the equation and using the nearest-integer function: \$\left[\frac{\varphi^n}{\sqrt5}\right]\$

This will speed up your program if you intend on calculating very large Fibonacci numbers.

Note: when calculating \$\varphi^n\$, use math.pow(x,y) because it uses floating point exponentiation and is always \$O(1)\$, whereas pow(x,y) and x**y can vary. For calculating \$\varphi\$ itself, there are many methods, here is an example.