Let A be an n by n matrix and consider the problem of computing the pth power Ap

Question

Let A be an n by n matrix and consider the problem of computing the pth power Ap. You could compute this the naive way as follows:

B = I (the identity matrix)

for i = 1 to p

do B = AB; (I assume you multiply using the classical method illustrated in class).

return B.

or you could use a more streamlined method that involves rewritting p as a sum of powers of 2. The worst thing that could happen is that your p will be of the form 2^m - 1 and thus a sum of m powers of 2 where m is approximately the logarithm to the base 2 of p. Your task is to evaluate (using big Theta the worst-case time complexity for computing A^p. This complexity is a function of both n and p. I assume I use the classical method to multiply matrices. In counting complexity I am ultimately counting numbers of multiplications of reals.

Explanation / Answer

Hey,

As you know class multiplication require O(n^2) if A is n x n matrix..

Here, loop is running p times,

so, total complexity= p.O(n^2)=O(p.n^2)

Hope this help you,

Don't forget to rate me 5 stars

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.