recursive fib, memoized fib, or O(1) fib?

Also, given that apache should run indefinitely, I would think the preferred result would be that fib is infinitely faster.

There is no O(1) fib.

Calculating that formula is not O(1), unless you have a way of calculating exponentiation, multiplication and subtraction all in O(1) time.

A closed form does not O(1) make

It contains n-th power. So it is O(logN).

In fact, since the fibonacci sequence grows as O(phi^n), we need O(n) digits to hold the n'th fibonacci number, so the fastest possible algorithm to compute the n'th fibonacci number must run in time Omega(n).

Not necessarily if you can parallelize computing the digits. Your average Pentium processor can compute a floating-point number with a mantissa of 16 decimal or 52 binary digits in one clock cycle, not 16 or 52. It does so by using enough silicon to compute them all in parallel.

That's only a constant factor improvement. What if you want to calculate 104 binary digits?

I couldn't determine which was the best, so I just calculated by hand instead