If you're computing the time complexity this way, then the simple linear dynamic programming is actually quadratic, and the matrix exponentiation algorithm is still faster.
Generally I would assume that multiplication and addition are constant time for big-O analysis, until given a reason otherwise. That might be less appropriate for fibonacci than most other problems though.
> Generally I would assume that multiplication and addition are constant time for big-O analysis, until given a reason otherwise.
I think this assumption can still be taken for the exponentiation version - I'm more nitpicking about the fact that there is a simple way to rephrase the problem (see below) to arrive at a different meaning of "linear" vs "sublinear" and it's better to be very explicit in cases where things may be misunderstood.
Rephrasing: fib(x) takes an x which is an array of bits of length m, which are the binary representation of number n. Return nth Fibonacci number.
Generally I would assume that multiplication and addition are constant time for big-O analysis, until given a reason otherwise. That might be less appropriate for fibonacci than most other problems though.