I think you meant n^3*log(K). Multiplication on two matrices would take O(n) per entry. And total #entries is n*n, thus multiplying 2 matrices takes O(n^3) To get a^(K), use simple divide-and-conquer technique. Since once one gets a^(K/2), to get a^(K) only needs to square it. Now we get T(K) = T(K/2)+O(multiply)--->T(K) = logK*O(multiply) = n^3*logK.
On Jan 12, 8:04 am, radha krishnan <radhakrishnance...@gmail.com> wrote: > Using Matrix Exponentiation technique > Complexity is n^3*(lg n) for matrix n x n > we need two n x n matrix to raise the matrix to power K .. > Correct me if am wronf > > On Wed, Jan 12, 2011 at 6:28 PM, bittu <shashank7andr...@gmail.com> wrote: > > How will you raise a n x n matrix to the power k efficiently. What's > > the time complexity and space complexity of you algorithm? How will > > you optimize this? > > > Thanks &Regards > > Shashank "Don't b Evil U Can Earn While U Learn" > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group > > athttp://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
