Binary exponentiation of matrix - complexity

Question

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)$

Answer 1

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.