Count Fibonacci numbers in given range in O(Log n) time and O(1) space - GeeksforGeeks

Count Fibonacci numbers in given range in O(Log n) time and O(1) space - GeeksforGeeks
Given a range, count Fibonacci numbers in given range. First few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ..

An Efficient Solution is to use previous Fibonacci Number to generate next using simple Fibonacci formula that fn = fn-1 + fn-2.

This looks simple solution, but many people got confused here as time complexity of this solution looks more.

int countFibs(int low, int high)

{

    // Initialize first three Fibonacci Numbers

    int f1 = 0, f2 = 1, f3 = 1;

 

    // Count fibonacci numbers in given range

    int result = 0;

 

    while (f1 <= high)

    {

        if (f1 >= low)

           result++;

        f1 = f2;

        f2 = f3;

        f3 = f1 + f2;

    }

 

    return result;

}

Time Complexity Analysis:
Consider the that Fibonacci Numbers can be written as below

So the value of Fibonacci numbers grow exponentially. It means that the while loop grows exponentially till it reaches ‘high’. So the loop runs O(Log (high)) times.

One solution could be directly use above formula to find count of Fibonacci Numbers, but that is not practically feasible (See this for details).

Read full article from Count Fibonacci numbers in given range in O(Log n) time and O(1) space - GeeksforGeeks