dark

# 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).

##### Previous Post ## Data types and variables

##### Related Posts ## system_engineering-devops part 2

What do the commands chmod, sudo, su, chown, chgrp do Linux file permissions How to represent each of the three sets of permissions (owner, group, and other) as a single digit ## Here are The Top 50 Linux Commands You Must Know as a Software Engineer

I have been compiling these Linux commands in my notes and i thought you could want to know one or two of them and i guess that is why you are here. now go through and see the one you need. ## How to Solve Coding Problem with White boarding

Table of Contents Hide Step 1: First Understand and Analyze the ProblemStep 2: Go Through The Sample Data…
Hey, if you have any questions and want to talk to one of our specialists chat up here: