Recursive vs. non-recursive implementations of Fibonacci sequence I have 2 functions to get the n-th fibonacci number. The 1st one uses recursive calls to calculate the power(M, n), while the 2nd function uses iterative approach for power(M, n). Theoretically (at least what I think), they should have the same speed O(log n), but why when I run both, the 2nd one is much slower than the 1st one?

def fib_1(n):
    from numpy import matrix
    def power(F, n):
        if n == 0 or n == 1: return matrix('1 1; 1 0', object)

        F = power(F, n &gt;&gt; 1) # n // 2
        F = F * F
        if n % 2 == 0:
            return F
        if n % 2 != 0:
            return F * matrix('1 1; 1 0', object)

    F = matrix('1 1; 1 0', object)
    F = power(F, abs(n)-1)
    return F[0,0] if n &gt; 0 else int((-1)**(n+1)) * F[0,0]


def fib_2(n):
    from numpy import matrix
    def power(F, n):
        M = matrix('1 1; 1 0', object)
        while n &gt; 0:
            if n &amp; 1 == 1:
                M = F * M
            n = n &gt;&gt; 1 # n = n // 2
            F = F * F
        return M

    F = matrix('1 1; 1 0', object)
    F = power(F, abs(n)-2)
    return F[0,0] if n &gt; 0 else int((-1)**(n+1)) * F[0,0]
Before we got any further, a word of warning. The complexity is only valid in a particular computational model.

The complexity of these algorithms is \$O(\log n)\$ only if the addition takes constant time. For large \$n\$ it is not the case.

Fibonacci numbers grow exponentially with n. It means that the number of bits grows linearly. Now we are in the Turing machine realm. The last addition itself takes \$O(n)\$, which is way more than \$\log n\$.

The overall complexity should be \$O(n\log{n})\$ in both cases. Why the two exhibit different performance?

The likely reason is that there is a subtle difference between them. fib_1 maintains just one matrix, F. fib_2 maintains two of them, F, M, and must do roughly twice as many reallocations as fib_1 does. The matrices contain huge numbers, and I expect that the memory management time dominates. Yet another factor the computational model shall now consider.