The time complexity of matrix multiplication is O(n^3). My professors taught me it is, but I never wondered why is it O(n^3), but not O(n^4), until I reviewed the code carefully a week ago. Let's see the pseudo code of a matrix multiplication
If you look at the above three boxes, you can say that the middle part is the one that contributes to complexity. Now take a look at it carefully..
There is an addition and a multiplication happening inside the three nested for loops. That means in the lowest kth loop we are multiplying n times and also adding n times. Then the time complexity should be O(n^4). I know that I will graduate in two more months, and I can leave my studies and go for a job, but this thing pestered my mind like anything. Suddenly I was moving across my room, scratching my head, searching for complexity all over the web. I settled down, only after I saw a video about matrix multiplication. It says
Since A[i][k] and B[k][j] are readily available constants, their multiplication takes a constant amount of time and need not be considered when dealing with complexity. But the term A[i][k]*B[k][j] is not readily available and that term is needed for addition. Hence you consider only the addition part, when you think of complexity. So inside the lowest for loop, we are doing only n operations
This has blown away my mind. So if two constants are readily available, their multiplication or addition takes a constant amount of time and can be ignored in terms of time complexity. Cool right ?
Update (15 April, 2012):
Am really sorry for this post. The complexity is O(n^3) anyway since in the lowest for loop you are doing 2 operations and hence the total operations would be 2*n^3, which will be O(n^3) anyway. As I told earlier in this post, if the constant multiplication is ignored the total operations would be n^3, which inturn becomes O(n^3)
#Consider A and B as two nxn matrices
#Initializing C as a nxn matrix filled with all zeros
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
C[i][j]=C[i][j]+A[i][k]*B[k][j]
Print C #C=AxB
There is an addition and a multiplication happening inside the three nested for loops. That means in the lowest kth loop we are multiplying n times and also adding n times. Then the time complexity should be O(n^4). I know that I will graduate in two more months, and I can leave my studies and go for a job, but this thing pestered my mind like anything. Suddenly I was moving across my room, scratching my head, searching for complexity all over the web. I settled down, only after I saw a video about matrix multiplication. It says
Since A[i][k] and B[k][j] are readily available constants, their multiplication takes a constant amount of time and need not be considered when dealing with complexity. But the term A[i][k]*B[k][j] is not readily available and that term is needed for addition. Hence you consider only the addition part, when you think of complexity. So inside the lowest for loop, we are doing only n operations
This has blown away my mind. So if two constants are readily available, their multiplication or addition takes a constant amount of time and can be ignored in terms of time complexity. Cool right ?
Update (15 April, 2012):
Am really sorry for this post. The complexity is O(n^3) anyway since in the lowest for loop you are doing 2 operations and hence the total operations would be 2*n^3, which will be O(n^3) anyway. As I told earlier in this post, if the constant multiplication is ignored the total operations would be n^3, which inturn becomes O(n^3)
No comments:
Post a Comment