What is the time complexity of computing Fibonacci terms with the 'fib(N) = [Phi^N – phi^N] / Sqrt[5]' formula?

user_11838630 0
Viewed 111

The normal recurrence of Fibonacci is Fib(N)= Fib(N-1)+Fib(n-2) which gives time complexity of 2^N. To reduce time complexity we have a formula below:

Fib(N) = [Phi^N – phi^N] / Sqrt[5] Source

where Phi= (1 + Sqrt[5]) / 2 and phi = (1-Sqrt[5])/2; or phi=Phi-1 Source

My code in java is below:

import java.util.*;
import java.lang.*;
public class Main
{
    public static void main(String[] args) {
        System.out.println(fib(50)+"");
    }
    
    static long fib(int N){
        final double sqrtFive=Math.sqrt(5);
        double Phi=(sqrtFive+1)/2;
        double phi=Phi-1;
        double fibN=(Math.pow(Phi,N)-Math.pow(phi,N))/sqrtFive;
        return (long) fibN;
    }
}

What is the time complexity of my code?

O(1)? because modern computer are superfast in computation so Math.pow(base,power) will be almost constant for any power.

O(logn+logn) means O(logn)? because I'm doing Math.pow(Phi,N)-Math.pow(phi,N) and Math.pow() function takes logN time.

I'm confused, please help me.

fibonacci math time-complexity algorithm java
1 Answers

Time Complexity is calculated in terms of the amount of iterations. This method of calculating fibonacci is actually O(1) because everything is done in 1 iteration without doing any recursion or looping.

Edit: If you only call this fibonacci method a couple times the runtime of the pow() operations doesnt matter. However, the more the method is called you do sorta have to take into account for the runtime of pow() as well. But in terms of Big O Notation, I would say that this is O(1)

user_149293490
Related