I have a question that is bugging me for around a 3 days, I first asked this question in stackoverflow but no one could answer it reasonably though they tried to help, so finally I found here as a last chance for help:
As you know multiplying 2 matrice is basically 6 subproblems and I made it 5 by the following manipulation,
so we can say that squaring matrice of 2*2 is O(n^log5) now my problem starts : I am trying to come up with two reasons that this can not be generalized for n*n, I wrote these reasonings in the exam and I got nothing for themso I understood that these are not correct :
1) If we multiply A*A (4*4) we will see that we get at lest 6 distinct multiplication and so T(n) >=6T(n/2)+n^2 and O is at least n^log6 which is n^epsolon greater than n^log5 so n^log6 is asymptotically slower
2) For multiplication of A*A when n=2 we have 5 multiplication and for n>2 we can say that at least 1 multiplication is added to the number of multiplication that we had for n=2 because at least one row and one column are added to our matrix which affects the # of multiplication so we can say that we foe n>2 we have at least 6 multiplication and it is enough for concluding that for n>2 we may get slower running time so we can not generalize n^log5
So I was suggested to look at it in this way: I should find things that I am doing in squaring a 2x2 that stop it from turning into a recursive step for square arrays. But the problem is that I am stuck and cannot go any further. what are does things that stop stop aquaring 2*2 matrice from turning into a recursive step for square arrays?
Thanks for your answer beforehand.:)