> This is why you have to specify exactly what you mean by the big-O notation you specify. He did specify it, it's O(log N) arithmetic operations. Note: I don

> This is why you have to specify exactly what you mean by the big-O notation you specify. He did specify it, it's O(log N) arithmetic operations. Note: I don't mean "assuming arithmetic operations take constant time, we can compute F(n) in O(log N) time", in which case you can correctly say that, since arithmetic operations don't take constant time in arbitrary precision arithmetic, we must be using fixed precision (or something essentially equivalent), in which case a lookup table takes O(1) time and O(precision) space. I mean "F(n) can be computed with O(log N) arithmetic operations". If I perform my arithmetic operations over arbitrary precision integers, and I implement simple arithmetic operations (so each arithmetic operation takes O((log n)^2) time), then F(n) takes O((log n)^3) time.