Dictionary key-value collection in C Sharp (C#) - Time & Space Complexity

Time Complexity: Dictionary key-value collection

O(n)

Understanding Time Complexity

When working with a dictionary, we want to know how fast we can find or add items as the dictionary grows.

We ask: How does the time to get or add a value change when there are more keys?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

var dict = new Dictionary<string, int>();

// Adding items
for (int i = 0; i < n; i++) {
    dict[$"key{i}"] = i;
}

// Accessing an item
int value = dict["key500"];
    

This code adds n key-value pairs to a dictionary and then accesses one value by its key.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding items to the dictionary inside the loop.
• How many times: The add operation runs n times, once per loop iteration.

How Execution Grows With Input

As we add more items, the total work grows roughly in direct proportion to the number of items.

Input Size (n)	Approx. Operations
10	About 10 add operations
100	About 100 add operations
1000	About 1000 add operations

Pattern observation: Doubling the number of items roughly doubles the total work done.

Final Time Complexity

Time Complexity: O(n)

This means adding n items takes time proportional to n, growing steadily as the dictionary gets bigger.

Common Mistake

[X] Wrong: "Accessing or adding items in a dictionary always takes longer as it grows because it searches through all keys."

[OK] Correct: Dictionaries use a special method to find keys quickly, so each add or access usually takes about the same short time no matter how many items there are.

Interview Connect

Understanding how dictionaries handle many items helps you explain why they are fast for lookups and inserts, a key skill in many programming tasks.

Self-Check

"What if we used a list instead of a dictionary to store key-value pairs? How would the time complexity for accessing a value by key change?"