On the Linear Time Algorithm For Finding Fibonacci Numbers

You're replying to a comment by Peter Krumins.

Dror Levin, here is how I did it:

First I created a Python program to time execution for an individual n:

```#!/usr/bin/python
#

import sys
from time import time

def LinearFibonacci(n):
""" Finds n-th Fibonacci number. n >= 1 """
fn = f1 = f2 = 1
for x in xrange(2, n):
fn = f1 + f2
f2, f1 = f1, fn
return fn

if __name__ == '__main__':
args = sys.argv[1:]
if len(args)<1:
print "Usage: prog.py <fib>"
sys.exit(1)
fib = int(args[0])
start = time()
LinearFibonacci(fib)
end = time()
print "%d, %f" % (fib, end-start)
```

Next I created a loop in shell to run the program 10 times for each individual value on n:

```for ((i=1;i<=200000;i+=1000)); do
for ((j=1;j<=10;j++)); do
./linear.py \$i >> linear.txt;
sleep 0.1
done;
done;
```

Next, I used an Awk program to calculate the average of 10 runs:

```awk -F, '
NR==1{this=\$1;prev=this}
{this=\$1}
this!=prev{printf "%d, %f\n", prev, a/10; prev=this; a=0}
{a+=\$2}
END {printf "%d, %f\n", prev, a/10}'
linear-txt > linear-averaged.txt
```

Finally I used the following script for GnuPlot to create the graph and fit the data with a quadratic function:

```filename = "linear-joined.txt"
f(x) = a*x**2 + b*x
fit f(x) filename via a, b
set title "Running time of Linear Fibonacci algorithm"
set xlabel "n-th fibonacci number" tc lt 3
set ylabel "running time in seconds" tc lt 3
set tics font "arial, 7"
set terminal gif size 480,360 font arial 9
set output './linear-fibonacci.gif'
plot filename with points pointtype 1 pointsize 0.6 title "LinearFibonacci(n)", f(x) title "O(x^2) approximation"
```

For the formulas I used this online latex generator.

Have fun!