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

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 think开发者_开发技巧ing 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.

---

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

---

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.

---

No, it's O(n). It would only be O(n^3) if there was a loop within a loop within a loop.

---

This is O(n).

As Where is O(n) this means that the cost of Where is approximately A x n, for some A.

Similarly as ToList and ForEach are also O(n) which means their cost is approximately B x n and C x n respective, for some B and some C.

This means that the total cost is roughly:

  (A x n) + (B x n) + (C x n)
= (A + B + C) x n 
= D x n

For some D (we never really cared what A, B and C were, so we also don't care what A + B + C is, so just call it D to make our equation simpler).

Hence this operation is O(n).

---

It's O(collection.Size) * O(SomeComplicatedOpInvolving_i).

---

collection.Where(i => i.condition) // is O(n) where n is the size of collection
.ToList() // is O(m) where m is the number if items with i.condition true
.ForEach(i => SomeComplicatedOpInvolving_i);  // O(m) where m is the number if items with i.condition true

Assuming that SomeComplicatedOpInvolving is O(1), e.g. it does not make longer if you have more items.

Given that

when m is never bigger then n, then 
O(n) + O(m) + O(m) == O(n) 

Then the snippet is O(n)