0

I'm kinda new to analyse algorithm and i wrote a different version of the Fib serie and i'm not quite sure about the worst case of the running time (assuming the basic operations counted are additions). Here is my code. 

int fib(int n){

    int tab[n]; 

    if (n<4){
        return n;
        }
        tab[0]=0;
        tab[1]=1;
        tab[2]=2;
        tab[3]=3;

    for(int i = 4; i<=n; ++i){

                tab[i] = tab[i-2] + (2*tab[i-4]) + 3;


        }

        return tab[n];

    }

I will say that the worst case here is W(n)= 2n-4 but..i really dont know. How do i analyse it properly?

Apex Predator
  • 171
  • 1
  • 3
  • 13
  • I cannot comment on the correctness but the time complexity of your code is `O(n)`. Its just a for loop executed `n` times where each iteration takes a constant time. – arunmoezhi Sep 29 '15 at 02:35
  • Ya, i know overall it's O(n) but i'm trying to figure out the exact worst case in this particular problem. – Apex Predator Sep 29 '15 at 02:40
  • 1
    what do you mean by `exact worst case`? – arunmoezhi Sep 29 '15 at 02:43
  • I will answer by an example: Even tough we know that the running time of the the iterative BS is O(lgn), if we want to be precise(by testing with small number) we will prove that it's actually O(lgn+1) :D not a big difference but just precision. – Apex Predator Sep 29 '15 at 03:24
  • "This is a very important thing to understand. You should never express an algorithm as “O(2N).” This is not a “more precise” or “better” answer than O(N); it’s only a confusing one. A so-called O(2N) algorithm is O(N) and should be expressed as such." --[What is the big O notation and how do I calculate it?](https://www.quora.com/What-is-the-big-O-notation-and-how-do-I-calculate-it) –  Sep 29 '15 at 03:33
  • See also: http://stackoverflow.com/a/18572977/539810 –  Sep 29 '15 at 03:39
  • Ok, i actually meant W(lgn+1) (W stands for Worst case), and sorry for not mentioning that, but i don't want to use BIG OH notation in this case. I do know how to compute it, the point of this problem is to see if i can actually analyse what's going on line by line. – Apex Predator Sep 29 '15 at 03:45

0 Answers0