Do I believe that this fragment is O (n ^ 3)?

Question

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

I am not looking for answers, saying that there is an easier way to do this, just consider it as a thought experiment.

First of all, am I right in thinking that these are three loops? Where() , ToList() and ForEach() ?
Secondly, (assuming that these are three loops), am I right in thinking that this is n to the power of 3 in a large O record?

Thanks to everyone.

Answer 1

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

Where() works in O (n) (if condition is a constant)

ToList() also does all the Where results, so O (n) also

ForEach() runs through the entire list created by ToList once, as well as O (n). I assume SomeComplicatedOpInvolving_i does not scale with number i ...

The key point here is that the loops are not nested, they start one after another, so the total execution time is 3 * O (n), which is the same as O (n).

Answer 2

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

Avoid using ToList (), which requires no reason to store O (n). Check out the blog post .

Answer 3

No, this is O(n) . It would only be O(n^3) if there were a loop in a loop inside a loop.

Answer 4

This is O(n) .

Since Where is O(n) , this means that the value of Where is approximately A xn , for some A

Similarly, ToList and ForEach also O(n) , which means that their cost is approximately equal to B xn and C xn respectively, for some B and some C

This means that the total cost is approximately equal to:

  (A xn) + (B xn) + (C xn) = (A + B + C) xn = D xn 

For some D (we were never interested in the fact that there were A , B and C , so it’s also not important for us that A + B + C , so just name it D to make our equation simpler).

Therefore, this operation is O(n) .

Answer 5

 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 SomeComplicatedOpInvolving is O (1), for example. it does not do more 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 fragment O (n)

Answer 6

This is O (collection.Size) * O (SomeComplicatedOpInvolving_i).