Am I right in thinking this snippet is O(n^3)?

Question

collection.Where(i => i.condition)
.ToList()
.ForEach(i => SomeComplicatedOpInvolving_i);

I'm not looking for answers telling me there is an easier way of doing this, just treat it as a thought experiment.

First up, am I right in thinking that this is three loops? Where(), ToList() and ForEach()?
Second of all, (assuming it is three loops) am I right in thinking this is n to the power of 3 in big O notation?

Thanks everyone.

Answer 1

No, actually. I think it should be O(n).

Where() runs in O(n) (assuming condition is constant)

ToList() runs over all the results of Where as well, so O(n) too

ForEach() runs over the entire list produced by ToList once, so also O(n). I assume SomeComplicatedOpInvolving_i doesn't scale with the number of i's...

The key point here is that the loops aren't nested, they run one after another - so total runtime is 3*O(n), which is the same as O(n).

Answer 2

No, they are not nested loops. It is O(n).

Avoid using ToList(), that costs O(n) storage for no good reason. Check this blog post.