Sign in to follow this  
Concentrate

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 this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this