The Importance of Algorithm Efficiency: Case Study of the Fibonacci Sequence

#algorithms #ruby

Why is algorithm efficiency important, and as a software engineer, should you care about it? The short (and probably obvious) answer is yes. But let's take a deeper look at how much of a difference an efficient algorithm can make by doing a case study with the Fibonacci Sequence.

If you've never heard of the Fibonacci Sequence, this is it:

0, 1, 1, 2, 3, 5, 8, 13, 21...

Essentially, it's a sequence of numbers where the nth number can be found by summing the (n-1)th number and the (n-2)th number. In simpler words, each number can be found by adding the two numbers that come before it.

Let's take a look at a simple iterative method for finding the nth number in the Fibonacci Sequence. Since we're software engineers, let's define the leading element as the 0^th element.

def simple_fib(n)
    if n == 0
        return 0
    end
    x = 0
    y = 1
    idx = 1 
    while idx < n
        temp = x + y
        x = y
        y = temp
        idx += 1
    end
    return y
end

This simple and intuitive method for finding the nth element in the fibonacci sequence has a time complexity of O(N). If you're not familiar with big-O notation, this article is a great, beginner-friendly guide to it.

Now let's also take a look at a much less intuitive but much more efficient algorithm. We're going to be multiplying matrices, so if you need a quick refresher on how that works, this source might help. Consider the following matrix:

M = [[1, 1],
     [1, 0]]

If we compute M², we're going to get

[[2, 1],
 [1, 0]]

And M³ =

[[3, 2],
 [2, 1]]

Let's increase the exponent once more, just for good measure. Computing M⁴ will give us

[[5, 3]
 [3, 2]]

Do you see the pattern? Take a look at the first element in the first row of each result matrix. These are the elements of the Fibonacci Sequence, starting at index 2!

That's cool, but how does that help with making the Fibonacci algorithm more efficient? Since taking matrix M to the power of n seems to help with finding the (n+1)^th element of the Fibonacci Sequence, we should be able to use an efficient algorithm for exponentiation to make a more efficient Fibonacci.

So let's take a brief detour and talk a bit about an efficient algorithm for exponentiation. Consider a method that computes mⁿ.

def exp(m, n)
    prod = 1
    for i in 0...n
        prod *= m
    end
    return prod    
end

The method above computes mⁿ in O(N) time, because it iterates through all numbers from 0 to N-1 to multiply. This seems OK, but we can do better.

Consider this method instead:

def exp(m, n)
    if n == 0
        return 1
    end
    if n%2 == 0
        return exp(m*m, n/2)
    else
        return exp(m*m, n/2) * m
    end
end

This method has a time complexity of O(log N), which is much better than O(N). So let's apply this method to matrix M. This method applied to a matrix will look slightly more complicated due to the matrix multiplication, but the runtime will be on the same order.

# This method will take in a 2x2 matrix and an integer exponent
def mat_exp(m, n)
    if n == 1
        return m
    end
    m1 = m[0][0]
    m2 = m[0][1]
    m3 = m[1][0]
    m4 = m[1][1]

    m_sq = [
        [m1*m1 + m2*m3, m1*m2 + m2*m4], 
        [m3*m1 + m4*m3, m3*m2 + m4*m4]
    ] 
    if n%2 == 0
        return mat_exp(m_sq, n/2)
    else
        r = mat_exp(m_sq, n/2)
        r1 = r[0][0]
        r2 = r[0][1]
        r3 = r[1][0]
        r4 = r[1][1]
        # Multiply matrix m to matrix r
        return [
            [r1*m1 + r2*m3, r1*m2 + r2*m4],
            [r3*m1 + r4+m3, r3*m2 + r4*m4]
        ]
    end
end

Since this method doesn't actually return a Fibonacci number but returns a matrix instead, we can call it as a helper method inside another method that will return the actual number that we're looking for.

def efficient_fib(n)
    if n == 0
        return 0
    end
    m = [[1, 1],[1, 0]]
    r = mat_exp(m, n - 1)
    return r[0][0]
end

Now we have an algorithm whose time complexity is O(log N), but will this actually help much with the performance of the method?

The answer is both yes and no. Let's say we're looking for the 5th number in the Fibonacci Sequence.

puts "Using simple_fib:"
t1 = Time.now
puts "The 5th element in the Fibonacci Sequence is #{simple_fib(5)}"
t2 = Time.now
puts "Time taken: #{t2 - t1}\n\n"

puts "Using efficient_fib:"
t3 = Time.now
puts "The 5th element in the Fibonacci Sequence is #{efficient_fib(5)}"
t4 = Time.now
puts "Time taken: #{t4 - t3}\n\n"

# => Using simple_fib:
# => The 5th element in the Fibonacci Sequence is 5
# => Time taken: 7.0e-06
# => 
# => Using efficient_fib:
# => The 5th element in the Fibonacci Sequence is 5
# => Time taken: 6.0e-06
# =>

So the efficient algorithm was about 1 μs faster than the simple one. It doesn't really seem like it was worth it to write an entirely new algorithm just to improve performance by 1 μs.

But what if we're looking for the 500th element instead of the 5th element?

t1 = Time.now
simple_fib(500)
t2 = Time.now
puts "Time taken using simple_fib: #{t2 - t1}\n\n"

t3 = Time.now
efficient_fib(500)
t4 = Time.now
puts "Time taken using efficient_fib: #{t4 - t3}\n\n"

# => Time taken using simple_fib: 7.7e-05
# =>  
# => Time taken using efficient_fib: 3.0e-05
# =>

This time there's a difference of 47 μs. So that's slightly better... Let's take a look now at what happens if we call both methods on n = 50000.

t1 = Time.now
simple_fib(50000)
t2 = Time.now
puts "Time taken using simple_fib: #{t2 - t1}\n\n"

t3 = Time.now
efficient_fib(50000)
t4 = Time.now
puts "Time taken using efficient_fib: #{t4 - t3}\n\n"

# => Time taken using simple_fib: 0.075218
# =>
# => Time taken using efficient_fib: 0.000832
# =>

This time there's a difference of 2 orders of magnitude! It seems that, when n is small, there's not much of a difference in the runtime of the methods, but when n gets larger, the difference in runtime also becomes larger. We can graph some more values of n to look at the trends.

The red points on the graph mark the runtime for different values of n for simple_fib, and the blue points mark the runtime for different values of n for efficient_fib. From the graph, it is apparent that the runtime increases rapidly for simple_fib as the value of n increases while the runtime for efficient_fib stays relatively low.

Although most programs with real applications probably won't be needing an efficient algorithm specifically for the Fibonacci Sequence, the purpose of this case study is to demonstrate how big of a difference an efficient algorithm can make. It is especially important when input values or the number of inputs is large, which is very likely if you're working on an app that has a substantial number of users. In the world of tech, a few seconds can be a big deal. You've experienced that yourself if you've ever felt frustration from a webpage or app taking more than 3 seconds to load.

If you are new to programming, it can be easy to find yourself thinking, "I'll be happy as long as I can get this code to work." However, I hope that this post has convinced you to take it a step further and also keep algorithm efficiency and performance optimization in mind as you continue your journey as a software engineer.