DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 964,423 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Marisa You
Marisa You

Posted on • Updated on

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

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...
Enter fullscreen mode Exit fullscreen mode

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 0th 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
Enter fullscreen mode Exit fullscreen mode

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]]
Enter fullscreen mode Exit fullscreen mode

If we compute M2, we're going to get

[[2, 1],
 [1, 0]]
Enter fullscreen mode Exit fullscreen mode

And M3 =

[[3, 2],
 [2, 1]]
Enter fullscreen mode Exit fullscreen mode

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

[[5, 3]
 [3, 2]] 
Enter fullscreen mode Exit fullscreen mode

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 mn.

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

The method above computes mn 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
Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
# =>
Enter fullscreen mode Exit fullscreen mode

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
# =>
Enter fullscreen mode Exit fullscreen mode

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
# =>
Enter fullscreen mode Exit fullscreen mode

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.

Alt Text

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.

Top comments (2)

Collapse
 
lghost profile image
Luis Arantes

Very good post Marisa. =)
It has been a long time since I last multiplied matrices, and browsing through your post made me do it again. xD

Collapse
 
marisayou profile image
Marisa You Author

Thank you! I'm glad you enjoyed it :)

Take a look at this:

Settings

Go to your customization settings to nudge your home feed to show content more relevant to your developer experience level. πŸ›