What is the Big O of linq .where?

I am doing some comparisons about where to filter out items from a list. I am unsure of doing it directly which would be O(n), or using .Where(). I made a simple example to test .Where() on a simple data set. There are n=100 items, and when I run the debugger on the line in the function BigO() it goes exactly 100 times making me think that .Where() is also O(n). What I couldn't figure out was where the data was being stored during the operation and I wasn't sure if that was adding any increased complexity.

Am I missing something, or is .Where() O(n)?

public class ListerFactory
{

 public class Lister
 {
  bool includeItem { get; set; }
 }

 List<Lister> someList { get; set; }

 public ListerFactory()
 {
  someList = new List<Lister>();
  BuildLister();
 }    

 public void BuildLister()
 {
  for(int i = 0; i < 100; i++)
  {
   var inc = new Lister();
   inc.includeItem = i % 2;
   someList.Add(inc);
  }
  BigO();
 }

 public void BigO()
 {
  someList = someList.Where(thisList => thisList.includeItem == true).ToList();
 }
}

c# linq big-o where-clause

Edit Report

-1

Depends on the source of the collection of course.

I disagree with @SLaks that the algorithm is O(1) because a query to Where() will keep searching for a candidate that matches the condition. In that sense it would be worst case O(n) with n the amount of work to yield the entire collection before the Where clause.

However he has a point it depends on the algorithm that yields the collection (for instance if it is a list that is already been build yielding the list is O(n) with n the number of items in the collection. Furthermore the algorithm that looks if there is a match is not necessarily O(1). If the yield algorithm is O(n) and the match algorithm O(m) the time complexity is O(n*m).

Take for instance a collection of integers:

int[] test = new int[] {1,2,3,4,5,6,7,8,9,10,7,5,0,1,5,6};

if you want to return all the integers who occur at least two times you could do this with a Where() clause:

test.Where(x => test.Count(y => x == y) >= 2);

The algorithm would be in O(n^2)

Secondly you can also build up the collection with a lazy setting:

public IEnumerable<int> GenerateCollection () {
    //some very complex calculation, here replaced by a simple for loop
    for(int i = 0; i < 150; i++) {
        yield return i;
    }
}

Your algorithm however first generates the list. So the timecomplexity is O(n).

Notice however if you iterate the entire collection after the where the timecomplexity is still O(n*m) and not O(n*n*m). That's because once a candidate has been matched, it will not be reconsidered.

answered 2012-03-25T23:01:43.717

What is the Big O of linq .where?

1 Answer

Your Answer