First, Single, and their OrDefault variants in C Sharp (C#) - Time & Space Complexity

Time Complexity: First, Single, and their OrDefault variants

O(n)

Understanding Time Complexity

When using First, Single, and their OrDefault variants in C#, it's important to know how long these methods take to find an item.

We want to understand how the time to find an element grows as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

var numbers = new List<int> {1, 2, 3, 4, 5};

// Find first even number
int firstEven = numbers.FirstOrDefault(n => n % 2 == 0);

// Find single number equal to 3
int singleThree = numbers.Single(n => n == 3);
    

This code looks for elements matching a condition in a list using FirstOrDefault and Single.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each element one by one until a match is found.
• How many times: Up to all elements in the list in the worst case.

How Execution Grows With Input

As the list grows, the time to find the element grows roughly in direct proportion.

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

Pattern observation: The number of checks grows linearly with the list size.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "First or Single methods instantly find the element regardless of list size."

[OK] Correct: These methods check elements one by one until they find a match, so bigger lists take more time.

Interview Connect

Understanding how these methods work helps you explain your code choices clearly and shows you know what happens behind the scenes.

Self-Check

"What if the list was sorted and you used a method that stops searching early? How would the time complexity change?"