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?"

Practice

1. What is a key requirement for creating a custom LINQ extension method in C#?

easy

A. It must be a static method inside a static class with this on the first parameter.

B. It must be an instance method inside any class.

C. It must return void and take no parameters.

D. It must be declared inside the Main method.

Solution

1. Step 1: Understand extension method structure

   Extension methods must be static methods inside static classes.

2. Step 2: Identify the special parameter usage

   The first parameter must have the this keyword to specify the type it extends.

3. Final Answer:

   It must be a static method inside a static class with this on the first parameter. -> Option A

4. Quick Check:

   Extension method = static + static class + this param [OK]

Hint: Remember: static method + static class + this param [OK]

Common Mistakes:

• Making the method non-static
• Forgetting the static class container
• Omitting the 'this' keyword on the first parameter

2. Which of the following is the correct syntax to declare a custom LINQ extension method named IsEven for IEnumerable<int>?

easy

A. public static bool IsEven(this IEnumerable<int> source) { ... }

B. public bool IsEven(IEnumerable<int> source) { ... }

C. static bool IsEven(IEnumerable<int> source) { ... }

D. public static bool IsEven(IEnumerable<int> source) { ... }

Solution

1. Step 1: Check method modifiers and parameters

   The method must be public static and have this before the first parameter to be an extension method.

2. Step 2: Verify the parameter type and method signature

   public static bool IsEven(this IEnumerable<int> source) { ... } correctly uses this IEnumerable<int> source and is static and public.

3. Final Answer:

   public static bool IsEven(this IEnumerable<int> source) { ... } -> Option A

4. Quick Check:

   Extension method syntax = public static + this param [OK]

Hint: Look for 'public static' and 'this' on first parameter [OK]

Common Mistakes:

• Missing 'this' keyword on the first parameter
• Not making the method static
• Incorrect access modifier

3. Given this custom LINQ extension method, what will be the output?

public static IEnumerable<int> GetPositive(this IEnumerable<int> source) {
    foreach (var num in source) {
        if (num > 0) yield return num;
    }
}

var numbers = new List<int> { -1, 0, 3, 5, -2 };
var result = numbers.GetPositive().ToList();
Console.WriteLine(string.Join(",", result));

medium

A. -1,0,3,5,-2

B. 0,3,5

C. 3,5,-2

D. 3,5

Solution

1. Step 1: Understand the extension method logic

   The method yields only numbers greater than zero from the source list.

2. Step 2: Apply the method to the list

   From the list [-1, 0, 3, 5, -2], only 3 and 5 are greater than zero and yielded.

3. Final Answer:

   3,5 -> Option D

4. Quick Check:

   Filter positive numbers = 3,5 [OK]

Hint: Focus on the 'if (num > 0)' filter condition [OK]

Common Mistakes:

• Including zero as positive
• Returning all numbers without filtering
• Confusing yield return with return

4. Identify the error in this custom LINQ extension method:

public static IEnumerable<int> FilterEven(IEnumerable<int> source) {
    foreach (var num in source) {
        if (num % 2 == 0) yield return num;
    }
}

medium

A. Cannot use 'yield return' inside a foreach loop.

B. Method should return void instead of IEnumerable<int>.

C. Missing 'this' keyword on the first parameter to make it an extension method.

D. The modulo operator '%' is not valid in C#.

Solution

1. Step 1: Check extension method signature

   The method lacks the this keyword on the first parameter, so it is not an extension method.

2. Step 2: Verify other syntax elements

   Using yield return inside a foreach is valid, and '%' is a valid operator in C#.

3. Final Answer:

   Missing 'this' keyword on the first parameter to make it an extension method. -> Option C

4. Quick Check:

   Extension method requires 'this' on first parameter [OK]

Hint: Extension methods always need 'this' on first parameter [OK]

Common Mistakes:

• Forgetting 'this' keyword
• Thinking 'yield return' is invalid in loops
• Misunderstanding the modulo operator

5. You want to create a custom LINQ extension method ToDictionaryByLength that converts an IEnumerable<string> into a Dictionary<int, List<string>>, grouping strings by their length. Which implementation correctly achieves this?

hard

A. public static Dictionary ToDictionaryByLength(IEnumerable<string> source) {
return source.ToDictionary(s => s.Length, s => new List<string> { s });
}

B. public static Dictionary ToDictionaryByLength(this IEnumerable<string> source) {
return source.GroupBy(s => s.Length)
.ToDictionary(g => g.Key, g => g.ToList());
}

C. public static Dictionary ToDictionaryByLength(this IEnumerable<string> source) {
var dict = new Dictionary();
foreach (var s in source) {
dict[s.Length] = new List<string> { s };
}
return dict;
}

D. public static Dictionary ToDictionaryByLength(this IEnumerable<string> source) {
return source.ToDictionary(s => s.Length, s => s);
}

Solution

1. Step 1: Understand grouping by length

   We need to group strings by their length, so GroupBy with key s.Length is correct.

2. Step 2: Convert groups to dictionary

   Use ToDictionary with group key and list of strings as value.

3. Step 3: Check other options

   public static Dictionary ToDictionaryByLength(IEnumerable<string> source) { return source.ToDictionary(s => s.Length, s => new List<string> { s }); } does not group; it tries to create dictionary with duplicate keys causing error. public static Dictionary ToDictionaryByLength(this IEnumerable<string> source) { var dict = new Dictionary(); foreach (var s in source) { dict[s.Length] = new List<string> { s }; } return dict; } overwrites values instead of adding to list. public static Dictionary ToDictionaryByLength(this IEnumerable<string> source) { return source.ToDictionary(s => s.Length, s => s); } tries to map to string instead of list.

4. Final Answer:

   public static Dictionary<int, List<string>> ToDictionaryByLength(this IEnumerable<string> source) { return source.GroupBy(s => s.Length) .ToDictionary(g => g.Key, g => g.ToList()); } -> Option B

5. Quick Check:

   GroupBy + ToDictionary with list = correct grouping [OK]

Hint: Use GroupBy then ToDictionary with list conversion [OK]

Common Mistakes:

• Not grouping before ToDictionary
• Overwriting dictionary entries instead of adding to list
• Returning wrong value types in dictionary