Big O — Calculating the right way

Our simple question is to find nth Fibonacci number and time complexity for the proposed algorithm.

1. Take the formula and write recursion formula and execute code.

public static int expExpFibonacci(int n) {
    if(n==1 || n == 2) return 1;
    return expExpFibonacci(n-1)+ expExpFibonacci(n-2);
}

Above code time complexity is O(2^n). which is exponential? (is it?)

2. Use dynamic programming, better code.

public static int expFibonacci(int n) {
    if(n==1 || n == 2) return 1;
    int f1 = 1, f2 =1;
    for(int i = 3; i <= n; i++) {
        int temp = f1+f2;
        f1 = f2;
        f2 = temp;
    }
    return f2;
}

Time complexity for above code is O(n). Yeah polynomial time.(Is it?)

3. Oh yeah, I know better one, we can get it in O(logn)

public static void product(int a[][], int b[][]) {
    int p = (a[0][0] * b[0][0]) + (a[0][1] * b[1][0]);
    int q = (a[0][0] * b[0][1]) + (a[0][1] * b[1][1]);
    int r = (a[1][0] * b[0][0]) + (a[1][1] * b[1][0]);
    int s = (a[1][0] * b[0][1]) + (a[1][1] * b[1][1]);
    a[0][0] = p;
    a[0][1] = q;
    a[1][0] = r;
    a[1][1] = s;
}
public static void power(int a[][], int n) {
    if(n == 0|| n==1) return;
    int base[][] = new int[][]{{1,1}, {1,0}};
    power(a, n/2);
    product(a, a);
    if(n%2 != 0) product(a, base);
}
public static int linearFibonacci(int n) {
    if(n==1 || n == 2) return 1;
    int base[][] = new int[][]{{1,1}, {1,0}};
    power(base, n-1);
    return base[0][0];
}

Time complexity for above code is O(log-n).

I have talked to many people about this problem, mostly they talk about 2nd approach and conclude it as polynomial time. 4 years back I was rejected in an interview for saying 2nd approach is not polynomial time algorithm and argued that it is actually exponential, i wrote a blog post and deleted back in time. But recently i have got focused into reading again and inspired by two of my friends(B, C). Couldn’t control write about this.

I have asked many people over past 7 years, mostly, they say it is polynomial and i get terrified.

I even saw this horror in many blogs and many commercial data structures books.

This time i am writing to make it clear to all guys out there.

Time complexity depends on input size and our input in here is n (a number). It means log-n (assume k) bits, that is called input size.

Let’s calculate complexities for all 3 approaches as we know and elaborate them.

1. 1st approach TC: O(2^n) = O(2^(2^log-n)) = O(2^(2^k)) , it is exponential to exponential w.r.t input size.
2. 2nd approach TC: O(n) = O(2^log-n) = O(2^k), it is exponential w.r.t input size.
3. 3rd approach TC( wrongly calculated ) : O(log-n) = O(k), it is polynomial time w.r.t input size.

Even though 3rd approach T.C. is polynomial it is not exactly O(log-n) but it is O(log³-n) = O(k³). it is because of addition and product of two numbers take O(log-n) and O(log²-n) takes respectively. (yes, in that case #1,#2 T.C. will increase log-n times)

Some people argued that O(n^number) means polynomial and argue sorting is done in polynomial time, that is ridiculous and horror.

For sorting problem, our input is n numbers(not a number) (if you calculate the input size in bits, it would be n*log-n and sorting T.C. can be either O(n*log-n*log-n) or O(n²*log-n). However usually one consider addition and multiplication done in O(1) and calculate the T.C. in general to not confuse student.

If you are still not convinced and argue that 2nd approach is polynomial (some call it linear time), congratulations you are able to validate a prime number in polynomial time without much thought.

P.S. I may not be a master in calculating T.C. for all algorithms but this fundamental one is definitely understood perfectly.

— — — — — — I will add those horrible references later — — — — — — — — —