Runtime of this short algorithm

Recommended Posts

This is a theoretical question so please don't say things like "in practice...".

So this the the question in hand :

Input is an n x n matrix A. Present an O(n^log_2(7)*log(m)) time algorithm to compute A^m, where m s an integer. You can assume m to be a integral power of 2.

So here was the algorithm I devised in psuedo-code:
calculate(A^m){ if(m == 1) return A; int mid = m/2; Compute(A^(mid)) -> M1 Compute(A^(mid+1)) -> M2 return M1*M2 using strassen's Algorithm; }

For informations,strassen's Algorithm runs in O(n^log_2(7)) which is equivalently O(n^2.81) to multiply a n x n matrix.

I argued that the running time in the above algorithm is O(n^log_2(7)*log(m)).By inspection, the recursion depth is log(m) and in each recursion depth, the running time is O(n^log_2(7)), hence the total running time is O(n^log_2(7)*log(m))

I wan't your guys input before I tell you what the running time my professor said it was.

Side note: The recurrence relation I think is:
T(n) = T(n/2) + T(n/2) + n^2.81
T(n) = 2T(n/2) + n^2.81

And using the master theorem, I get T(n) = O(n^2.81)?

I'm getting confused. Any help please?

Share on other sites
Compute(A^(mid+1)) -> M2

That line is your problem. You're making an unnecessary extra recursive call per step, which leads to an exponential increase in the complexity.

This causes your algorithm to be O(n^2.81 * m)

What you should do is just return M1*M1

Share on other sites
Oh shit ur right, fukkkk. Thanks.

Create an account

Register a new account

• Forum Statistics

• Total Topics
628375
• Total Posts
2982310

• 10
• 9
• 14
• 24
• 11