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