Rahul Dazz Das

Greenhorn

Posts: 10

Piet Souris

Rancher

Posts: 1979

67

Rahul Dazz Das

Greenhorn

Posts: 10

Piet Souris

Rancher

Posts: 1979

67

Rahul Dazz Das

Greenhorn

Posts: 10

posted 1 year ago

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 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?

Piet Souris

Rancher

Posts: 1979

67

Rahul Dazz Das

Greenhorn

Posts: 10

posted 1 year ago

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 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!).

Piet Souris

Rancher

Posts: 1979

67

posted 1 year ago

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.

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.

posted 1 year ago

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

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

posted 1 year ago

Sir, Thanks for enlightening.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

Rahul Dazz Das

Greenhorn

Posts: 10

posted 1 year ago

Thanks mate.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.

It is sorta covered in the JavaRanch Style Guide. |