There is no constant time implementation. Binet's formula uses exponentiation, which gives us log(n) time.