@Koup: No, I meant O(n^3 log k). Sorry. Dave On Sunday, January 20, 2013 3:09:00 AM UTC-6, Koup wrote:
> I need to multiply an array A by it self. Is there an algorithm that does > array multiplication with complexity O(n^2)?Doesn't it take at least O(n^3)? > > On Sun, Jan 20, 2013 at 12:44 AM, Dave <dave_an...@juno.com > <javascript:>>wrote: > >> @Guneesh: I think you mean to say that the complexity of both the >> iterative and recursive algorithms is O(n^3 log k), using the notation of >> the original poster (A is n-by-n, and it is to be raised to the power k). >> >> If what you really need is a way to calculate A^k * x, for some vector x, >> it may be cheaper to use matrix-vector multiplication k times; this will be >> O(n^2 * k). >> >> Dave >> >> On Saturday, January 19, 2013 7:30:50 AM UTC-6, Guneesh wrote: >> >>> both recursive and iterative codes are O(nlogn) algos.. >>> but memory will be more in recursion.. >>> so we will prefer iteration >> >> -- >> >> >> > > --
