Sign Up for Our Newsletter

Subscribe to our newsletter to get our newest articles instantly!

What is the Big O notation?

Evaluating the time complexity of an algorithm

int Fibonacci(int number)
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);

The function above is an example of a recursive implementation of the Fibonacci sequence. The function takes an integer as input and returns the corresponding Fibonacci number.

To evaluate the time complexity of this algorithm, we can look at how the number of operations performed by the algorithm relates to the input number. In this case, we can see that the function calls itself twice for each number, and it does this for every number up to the input number. This means that the number of function calls is proportional to the Fibonacci sequence, which is approximately equal to the Golden Ratio raised to the power of the input number.

This leads to an exponential time complexity of O(phi^n) where phi is the golden ratio, which is an irrational number approximately equal to 1.6180339887. This is a very bad time complexity for large input, it is not suitable for larger inputs.

It’s important to note that this algorithm is not a good solution for finding larger Fibonacci numbers as the number of function calls increases exponentially with the input number. A better solution would be a dynamic programming approach where the function stores the already calculated Fibonacci numbers in an array and uses them to calculate the next number. That way the time complexity would be O(n). 

See also  alx-low_level_programming/0x03-debugging
Leave a Reply

Your email address will not be published. Required fields are marked *

Previous Post
Python 3 tutorial series outline 3

Data types and variables

Please Leave a comment on comment section, let me know what you think about this article.

Related Posts
Hey, if you have any questions and want to talk to one of our specialists chat up here:
Chat me up