Predicate delegate type in C Sharp (C#) - Time & Space Complexity

Time Complexity: Predicate delegate type

O(n)

Understanding Time Complexity

We want to understand how long it takes to run code that uses a Predicate delegate.

Specifically, how the time grows when checking items with a Predicate.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool CheckAll(int[] numbers, Predicate<int> condition)
{
    foreach (int num in numbers)
    {
        if (!condition(num))
            return false;
    }
    return true;
}
    

This code checks if all numbers in an array satisfy a condition using a Predicate delegate.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each number in the array and calling the Predicate.
• How many times: Up to once per element, stopping early if condition fails.

How Execution Grows With Input

As the array gets bigger, the number of checks grows roughly the same size.

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

Pattern observation: The work grows directly with the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to check all items grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "Using a Predicate makes the check instant or constant time."

[OK] Correct: The Predicate is just a function called for each item, so time depends on how many items you check.

Interview Connect

Understanding how delegates like Predicate affect performance shows you know how code runs behind the scenes.

Self-Check

"What if the method returned true as soon as one item matches the condition instead of checking all? How would the time complexity change?"