Win a copy of Java EE 8 High Performance this week in the Java/Jakarta EE forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

Greenhorn
Posts: 14
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

Master Rancher
Posts: 2311
76
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: 14

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
Master Rancher
Posts: 2311
76
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: 14

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
Master Rancher
Posts: 2311
76
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: 14

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
Master Rancher
Posts: 2311
76
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.

author
Sheriff
Posts: 23364
127
• 1

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: 14

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: 14

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.

 Let nothing stop you! Not even this tiny ad: The WEB SERVICES and JAX-RS Course https://coderanch.com/t/690789/WEB-SERVICES-JAX-RS