List patterns in C Sharp (C#) - Time & Space Complexity

Time Complexity: List patterns

O(n)

Understanding Time Complexity

When working with lists, it is important to know how the time to complete tasks changes as the list grows.

We want to understand how operations like searching or iterating through a list take more or less time depending on the list size.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

bool found = false;
foreach (int num in numbers)
{
    if (num == target)
    {
        found = true;
        break;
    }
}

This code searches for a target number in a list by checking each item one by one until it finds the target or reaches the end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the list items one by one.
• How many times: Up to once for each item in the list until the target is found or the list ends.

How Execution Grows With Input

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

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 operations grows directly with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the target grows in a straight line with the list size.

Common Mistake

[X] Wrong: "Searching a list always takes the same time no matter how big it is."

[OK] Correct: Because the program may need to check many items, the time grows as the list grows.

Interview Connect

Understanding how list operations scale helps you explain your code choices clearly and shows you know how to write efficient programs.

Self-Check

"What if we used a sorted list and applied binary search? How would the time complexity change?"