2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Mar 13, 2021 at 15:42
  • $\begingroup$ Note that your $n/2$ is really $\lfloor n/2 \rfloor$. $\endgroup$ Mar 13, 2021 at 15:42
  • $\begingroup$ Yes, but if we take algorithm with cost $k^3$ is my solution correct? $\endgroup$
    – Nerwena
    Mar 13, 2021 at 15:47
  • $\begingroup$ The solution to $T(n) = T(\lfloor n/2 \rfloor) + C$ is $T(n) = C \lfloor \log_2 n \rfloor + T(1)$. $\endgroup$ Mar 13, 2021 at 15:51
  • $\begingroup$ Why are you adding $T(1)$? $\endgroup$
    – Nerwena
    Mar 13, 2021 at 15:54

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.