Task and Task of T types in C Sharp (C#) - Time & Space Complexity

Time Complexity: Task and Task of T types

O(n)

Understanding Time Complexity

When working with asynchronous code using Task and Task<T>, it's important to understand how the time to complete tasks grows as you start more tasks or wait for their results.

We want to see how the time needed changes when handling multiple tasks.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    public async Task<int> SumAsync(int[] numbers)
    {
        var tasks = new List<Task<int>>();
        foreach (var num in numbers)
        {
            tasks.Add(Task.Run(() => num));
        }
        var results = await Task.WhenAll(tasks);
        return results.Sum();
    }
    

This code creates a task for each number to return it asynchronously, waits for all tasks to finish, then sums the results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Creating and running one task per number in the input array.
• How many times: Once for each element in the input array (n times).

How Execution Grows With Input

As the input array grows, the number of tasks created and awaited grows proportionally.

Input Size (n)	Approx. Operations
10	About 10 tasks created and awaited
100	About 100 tasks created and awaited
1000	About 1000 tasks created and awaited

Pattern observation: The work grows directly with the number of input items, so doubling input doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete grows linearly with the number of tasks you start and wait for.

Common Mistake

[X] Wrong: "Starting many tasks at once makes the program run instantly regardless of input size."

[OK] Correct: Even though tasks run asynchronously, creating and waiting for many tasks still takes time proportional to how many tasks there are.

Interview Connect

Understanding how asynchronous tasks scale helps you write efficient code and explain your reasoning clearly in interviews.

Self-Check

"What if we changed Task.WhenAll to await each task one by one? How would the time complexity change?"