Thanks so much for your comment. I had actually tried -O3 during my tests and didn't notice a huge difference in this particular example.

fots ~ $ gcc -O -o fib fib.c

fots ~ $ time ./fib

433494437

real 0m0.749s

user 0m0.743s

sys 0m0.003s

fots ~ $ gcc -O3 -o fib fib.c

fots ~ $ time ./fib

433494437

real 0m0.747s

user 0m0.742s

sys 0m0.003s

fots ~ $ gcc -O2 -o fib fib.c

fots ~ $ time ./fib

433494437

real 0m0.741s

user 0m0.737s

sys 0m0.003s

Clearly this is just a little mathematical algorithm and more real-world problems would likely produce a more dramatic difference.

What sort of differences did you see on your end?