O(1)というのはご機嫌に速いということ？

「実際に起こりうる状況ではご機嫌に速い」という意味で「O(1)」と書くことがあるわけですが、誤解が生じるのでやめたほうがいいと思います

たとえばn桁の足し算は、2つの整数および結果が適当なレジスタに収まるうちは、1クロック（程度）でできるのでご機嫌に速いわけですが、O(1)というわけではもちろんなく、O(n)だと考えるのがふつうでしょう

もう少し厳密に言うと、精度に限りがあるのであれば、指数関数もO(1)でよい、ということです（ベキ乗はO(1)でOK?）

厳密に言えば、こういう言い方は許されないはずです。精度に限りがあるのなら、結果の入ったテーブルを使うことで、どんな関数でもご機嫌に速く計算できます。もっとも、テーブルを作るのに時間がかかるわけですが、

こうして一度出した結果を覚えておいて、あればそれを使うという方法はメモ化(memoization)として知られています。見ての通り、定義通りなナイーブな計算法を使っているのに、O(2n)がO(1)（厳密には、最初の一回だけO(n))になってしまうのです。（フィボナッチ数列にO()を学ぶ）

ということが許される状況でなら、まあ、いいのでしょう。厳密には、「最初の1回だけO(n)になる」というような表現は許されないはずですが

追記：元サイトに載っているコードが正しい結果を返すのはn=70まで（Cだと再現性がないかもしれない。確かめたければJavaのStrictMathとかで）。そのくらいだと、もっともナイーブな実装でなければ、テーブルを作るのもそれを覚えてのも簡単。計算量や計算時間について真剣に考えるものではないのかも。

補足：カジュアルなO記法