It's O(M(n)) where M(n) is the complexity of the algorithm used for multiplying n-bit integers. To see why, note that each step of the matrix powering or fast

It's O(M(n)) where M(n) is the complexity of the algorithm used for multiplying n-bit integers. To see why, note that each step of the matrix powering or fast doubling algorithm 1) costs a constant C number of multiplications, and 2) roughly doubles the number of bits. F(n) has b = O(n) bits, so the cost is essentially C M(b) + C M(b/2) + C M(b/4) + ... <= 2 C M(b) = O(M(n)), using the natural assumption that M(2x) >= 2M(x).