Computational Complexity of Setting Matrix Elements to a Value

Hello,

I have a problem where I am implementing a projection onto some set (could go into more detail if need be, but for now I'll keep it at that). I know this projection can be implemented really efficiently in MATLAB by simply setting the the entire row of a matrix to 0, while keeping all the other elements the same. Now, I am rather new to the concept of computational complexity, so I was wondering if someone could help me with figuring this out. I believe given a matrix in ℝ, this complexity should be on , since we are setting N elements to zero?

If that is not the correct intuition, could someone please assist me in this topic?

Thanks

[Sindar]

That reasoning sounds correct to me (you could think of it as doing N multiplications), but I don't know how useful it is in practice. As you say, this is really efficient, so I'd expect almost any other part of the program to take longer, regardless of scaling. Plus, the actual time will depend a lot on the specifics of memory (is the data stored row-column or column-row? How does the matrix size compare to cache? What tricks does Matlab do when inserting the same value in many locations?)

[per isakson]

There are a few submissions on computational complexity in the FEX.

[Sean T]

Thanks for the answers, not sure how to reply directly.

Sindar, you are correct - - the other parts of the program do take longer. However, I was trying to show that I could reduce the most computationally expensive part (which required an SVD) into a simple projection, thus being dominated by the other, less computationally expensive parts of the algorithm. In any case, thanks for some further intuition into this problem.

per isakson, thanks for the resources. I will be sure to take a look.

[Sindar]

In this case, I think it's fair to say you've improved it to trivial cost, changing the bottleneck to a different part of the algorithm. This is more informative than a complexity scale, but if they really want it, you could say something like "O(N) with a very small coefficient"