Binary exponentiation of matrix - complexity I want to calculate complexity for binary exponentiation of matrix of size $k$. Let's say that I'm using the simplest approach to multiply matrices (so with three for loops). The complexity of this operation would be $O(n^3)$. Now, the powering of matrix. Pseudo code (n is the power, A matrix):
power(n, A)
 if n == 0
  return 1
 else
   res = power(n/2, A)
   if n%2 == 0
     return res * res
   else 
     return res * res * A

If I write the equation:
$$T(n)=T(n/2) + O(k^3)$$
where $T(n)$ is the complexity, is it correct to think of cost to be $O(k^3)$?
Then we sum
$$\sum_{i=0}^{\log_2n}O(k^3) = O(k^3\log_2n)$$
and for us $k=27$ is constant.
Hence $T(n)=O(\log_2n)$
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.