Custom LINQ extension methods in C Sharp (C#) - Time & Space Complexity

Time Complexity: Custom LINQ extension methods

O(n)

Understanding Time Complexity

When we create custom LINQ extension methods, we want to know how their speed changes as the input list grows.

We ask: How many steps does the method take when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public static IEnumerable<T> CustomWhere<T>(this IEnumerable<T> source, Func<T, bool> predicate)
{
    foreach (var item in source)
    {
        if (predicate(item))
            yield return item;
    }
}
    

This method filters items from a list based on a condition, returning only those that match.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each item in the input list once.
• How many times: Exactly once for every item in the list.

How Execution Grows With Input

As the list gets bigger, the method checks each item one by one.

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

Pattern observation: The number of steps grows directly with the size of the list.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "The method runs faster because it stops early when it finds a match."

[OK] Correct: The method still checks every item because it must find all matches, not just one.

Interview Connect

Understanding how your custom LINQ methods scale helps you write efficient code and explain your thinking clearly in interviews.

Self-Check

"What if we changed the method to use nested loops to compare each item with every other item? How would the time complexity change?"