LINQ with custom objects in C Sharp (C#) - Time & Space Complexity

Time Complexity: LINQ with custom objects

O(n)

Understanding Time Complexity

When using LINQ with custom objects, it's important to understand how the time to run queries changes as the number of objects grows.

We want to know how the program's work increases when we have more items to search or filter.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

var people = new List<Person> {
    new Person("Alice", 30),
    new Person("Bob", 25),
    new Person("Charlie", 35)
};

var result = people.Where(p => p.Age > 28).ToList();
    

This code filters a list of custom Person objects to find those older than 28 years.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The Where method loops through each Person object to check the age condition.
• How many times: It runs once for every person in the list.

How Execution Grows With Input

As the number of people increases, the program checks each one once.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The number of checks grows directly with the number of people.

Final Time Complexity

Time Complexity: O(n)

This means the time to filter grows in a straight line as the list gets bigger.

Common Mistake

[X] Wrong: "LINQ queries run instantly no matter how many items there are."

[OK] Correct: LINQ still checks each item one by one, so more items mean more work and more time.

Interview Connect

Understanding how LINQ works with custom objects helps you explain how your code handles data efficiently, a useful skill in many coding discussions.

Self-Check

"What if we changed the filter to check two conditions instead of one? How would the time complexity change?"