@jammy: Sorry for wrong answer thats O(n^3 *lg(K))
On Thu, Jan 13, 2011 at 12:28 AM, Jammy <xujiayiy...@gmail.com> wrote: > 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. > > -- 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.
