# 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 cost depends on the algorithm you use to multiply matrices. If $k$ is constant, then whatever algorithm you use, the cost to multiply two matrices will be constant. Mar 13, 2021 at 15:42
• Note that your $n/2$ is really $\lfloor n/2 \rfloor$. Mar 13, 2021 at 15:42
• Yes, but if we take algorithm with cost $k^3$ is my solution correct? Mar 13, 2021 at 15:47
• The solution to $T(n) = T(\lfloor n/2 \rfloor) + C$ is $T(n) = C \lfloor \log_2 n \rfloor + T(1)$. Mar 13, 2021 at 15:51
• Why are you adding $T(1)$? Mar 13, 2021 at 15:54

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.