Binary exponentiation of matrix - complexity
The solution of the recurrence
$$
T(n) = T(\lfloor n/2 \rfloor) + O(1)
$$
(this is the correct form of your recurrence) is $T(n) = O(\log n)$. If you want to be more accurate, the solution of the recurrence
$$
T(n) = T(\lfloor n/2 \rfloor) + C
$$
is (for $n \geq 1$)
$$
T(n) = C\lfloor \log_2 n \rfloor + T(1).
$$
In your case $C$ is not really constant, but rather depends on the parity of $n$. Accordingly, we can consider the recurrence
$$
T(n) = T(\lfloor n/2 \rfloor) + C_{n \bmod 2},
$$
whose solution is
$$
T(n) = C_1 \#_1(\mathrm{bin}(n)) + C_0 \#_0(\mathrm{bin}(n)) + T(0);
$$
here $\mathrm{bin}(n)$ is the binary representation of $n$, and $\#_0,\#_1$ is the number of $0$-s and $1$-s, respectively.