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_and_da...@juno.com> 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 > > -- > > > --
