Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Asymptotic behavior of Matrix Addition  RSS feed

 
Rahul Dazz Das
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can anyone help understand (with reasons) the asymptotic behaviour of below algorithm as input size increases?

Input:
Two n x m matrices A and B

Output:
The matrix C = A + B

Algorithm:
for i from 1 to n do
for j from 1 to m do
Cij = Aij + Bij
end for
end for
 
Piet Souris
Rancher
Posts: 1979
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Rahul,

assuming you mean the time complexity, you perfom m additions, and that is done n times, so it is an O(?) complexity.
If you mean sometinh else, can you elaborate a little?
 
Rahul Dazz Das
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:hi Rahul,

assuming you mean the time complexity, you perfom m additions, and that is done n times, so it is an O(?) complexity.
If you mean sometinh else, can you elaborate a little?
Yes I meant Time complexity. But what would be the value of O(?) complexity.
 
Piet Souris
Rancher
Posts: 1979
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How many elements does an N x M matrix have? And for each element you perform an addition (Aij + Bij). So, what time complexity do we have?
 
Rahul Dazz Das
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:How many elements does an N x M matrix have? And for each element you perform an addition (Aij + Bij). So, what time complexity do we have?
N x M matrix would have NM elements, for example a 3 x 4 matrix will have 12 elements. I would like to understand how would the algorithm behave if I double the number of elements, say to 24. Linear or Quadratic?
 
Piet Souris
Rancher
Posts: 1979
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Exactly, and for each element of C we need to preform an addition. So what time complexity do we get? (hint: it is as simple as you think!).
 
Rahul Dazz Das
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:Exactly, and for each element of C we need to preform an addition. So what time complexity do we get? (hint: it is as simple as you think!).
Majority of folks say it will be "quadratic", I could also see few stating it to be of  "linear" behaviour. I know it's simple but I am confused as no one is giving a proper justification for the answer.
 
Piet Souris
Rancher
Posts: 1979
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay, well it simply is O(NM).

If N = M, then we have quadratic indeed, and given M, you could say it is linear in N.

Sometimes it is very hard to say something about the complexity. Measuring it by performing
many operations and counting the number of operations is also not very easy.

 
Henry Wong
author
Sheriff
Posts: 23283
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rahul Dazz Das wrote:Majority of folks say it will be "quadratic", I could also see few stating it to be of  "linear" behaviour. I know it's simple but I am confused as no one is giving a proper justification for the answer.


In my opinion, I think that it is a bit more subtle than that. Keep in mind that it depends on when the number "N" grows to infinity. And if there are more than one growing value, then it is the fastest growing one.

So, which "N" is being referred to here? Is it the number of rows? the number of columns? the number of actual elements in the array? ... which, interestingly, all have the same time complexity.

The subtle issue here is ... what if you don't know which grows faster? In this example, what if both N and M are growing fast? ... or meaning that there is actually a formula between the two? In that case, you can use the formula to eliminate one of the variables first, in order to get the time complexity in terms of the other one.


Anyway, I would guess that those who say it is linear, are picking either row, column, or the number of units as the basis. And those who are saying quadratic are assuming that N=kM in terms of growth, and then picking either row or column. I guess, since the example never mentioned the relationship of N to M, that either assumption is valid.

Henry
 
Rahul Dazz Das
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Henry Wong wrote:
Rahul Dazz Das wrote:Majority of folks say it will be "quadratic", I could also see few stating it to be of  "linear" behaviour. I know it's simple but I am confused as no one is giving a proper justification for the answer.


In my opinion, I think that it is a bit more subtle than that. Keep in mine that it depends on when the number "N" grows to infinity. And if there are more than one growing value, then it is the fastest growing one.

So, which "N" is being referred to here? Is it the number of rows? the number of columns? the number of actual elements in the array? ... which, interestingly, all have the same time complexity.

The subtle issue here is ... what if you don't know which grows faster? In this example, what if both N and M are growing fast? ... or meaning that there is actually a formula between the two? In that case, you can use the formula to eliminate one of the variables first, in order to get the time complexity in terms of the other one.


Anyway, I would guess that those who say it is linear, are picking either row, column, or the number of units as the basis. And those who are saying quadratic are assuming that N=kM in terms of growth, and then picking either row or column. I guess, since the example never mentioned the relationship of N to M, that either assumption is valid.

Henry
Sir, Thanks for enlightening.
 
Rahul Dazz Das
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:Okay, well it simply is O(NM).

If N = M, then we have quadratic indeed, and given M, you could say it is linear in N.

Sometimes it is very hard to say something about the complexity. Measuring it by performing
many operations and counting the number of operations is also not very easy.

Thanks mate.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!