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
@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,
I want to get the power of an matrix. I mean lets say my matrix is A i
wanna get the A ^k.
I have though the simple algorithm that gives me O(n^3).I though I could do
some kind of a change to modify it and be faster. I could use the algorithm
that is used to get the power of a number that
consider code to find n^k where n is an integer
int power()
{
int ans=1,val=1;
while(k)
{
val=val*n;
if(k1)ans=ans*val;
k=k1;
}
return ans;
}
now if n is is a matrix all you have to do is replace * by matrix
multiplication algorithm
--
Just to make sure I understood your code that if means that in case the k
is an odd number just multiply the accumulator 1 time with the val and
continue with even k.A question I have is if a recursive implementation
of this would be any faster?
Τη Σάββατο, 19 Ιανουαρίου 2013 1:06:25 μ.μ.
both recursive and iterative codes are O(nlogn) algos..
but memory will be more in recursion..
so we will prefer iteration
--
@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
@Guneesh: I don't think your code is correct. You want val to take on the
values n, n^2, n^4, n^8, ..., whereas in your code, val takes on the values
1,n, n^2, n^3, The algorithm should be more like this:
int power()
{
int ans=1,val=n;
while(k)
{
if(k1)ans=ans*val;
k=k1;
@dave thanks for correcting :)
--
