Program Fibonacci

1 program fibonacci (input, output);
2 {compute the Fibonacci number F[n]}
3 type natural=0..maxint;
4var fnm1, fnm2, fn, n, i : natural;
5 begin
6     readln(n);
7     if n<=1 then writeln(n) F[0]=0 and F[1]=1}
8         else
9         begin {compute F[n]}
10              fnm2:=0; fnm1:=1;
11              for i:=2 to n do
12              begin
13                 fn:=fnm1 + fnm2;
14                 fnm2:=fnm1;
15                 fnm1:=fn;
16             end; {of for }
17             writeln(fn);
18         end; {of else}
19 end {of Fibonacci}

To analyze the complexity of this program, we need to consider the two cases: (i) n=0 or 1, and (ii) n>1. We shall count the total number of statement executions and use this as a measure of the time complexity of the program. Further, we note that only executable statements contribute to the complexity of the program. Thus type and variable declarations, begin statements will not be counted as they simply designate the start of statement blocks.

When n = 0 or 1, lines 6,7 and 19 get executed once each. We shall give line 7 a count of 2 (one for the conditional and one for the then clause). The total statement count for this case is therefore 4. When n>1, the for loop of lines 11-16 gets executed. Line 11 gets executed n times while lines 12-16 get executed n-1 times each (note that the last time line 11 is executed, i is incremented to n+1 and the loop exited.) Each execution of line 10 counts as 2 towards the statement count as line 10 contains two statements. The contribution of the remaining lines is zero.