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?"

Practice

1. What is the main purpose of a Dictionary in C#?

easy

A. To create graphical user interfaces

B. To store data in a sequential list

C. To perform mathematical calculations

D. To store data as key-value pairs for quick access

Solution

1. Step 1: Understand the Dictionary concept

   A Dictionary stores data as pairs where each key is linked to a value for fast lookup.

2. Step 2: Compare with other options

   Options B, C, and D describe lists, math, and UI, which are unrelated to Dictionary's purpose.

3. Final Answer:

   To store data as key-value pairs for quick access -> Option D

4. Quick Check:

   Dictionary = key-value pairs [OK]

Hint: Remember: Dictionary = keys + values for fast lookup [OK]

Common Mistakes:

• Confusing Dictionary with List
• Thinking Dictionary stores only values
• Assuming Dictionary is for UI or math

2. Which of the following is the correct way to add a key-value pair to a Dictionary<int, string> named dict?

easy

A. dict.Add(1, "apple");

B. dict.Insert(1, "apple");

C. dict["1"] = "apple";

D. dict.Put(1, "apple");

Solution

1. Step 1: Recall Dictionary methods

   The method to add a new key-value pair is Add(key, value).

2. Step 2: Check options

   Only dict.Add(1, "apple"); uses Add. dict[1] = "apple"; uses indexer which sets or updates but is not the method to add explicitly.

3. Final Answer:

   dict.Add(1, "apple"); -> Option A

4. Quick Check:

   Add() method adds key-value pair [OK]

Hint: Use Add() to insert new pairs, indexer to update [OK]

Common Mistakes:

• Using Insert or Put which don't exist
• Confusing Add() with indexer for adding
• Trying to add with wrong method name

3. What will be the output of this C# code?

var dict = new Dictionary<int, string>();
dict.Add(1, "one");
dict[2] = "two";
Console.WriteLine(dict[1] + ", " + dict[2]);

medium

A. two, one

B. 1, 2

C. one, two

D. Runtime error

Solution

1. Step 1: Understand dictionary additions

   Key 1 is added with value "one" using Add(). Key 2 is set to "two" using indexer.

2. Step 2: Check output of Console.WriteLine

   It prints values for keys 1 and 2 joined by comma: "one, two".

3. Final Answer:

   one, two -> Option C

4. Quick Check:

   dict[1] = one, dict[2] = two [OK]

Hint: Indexer sets or updates; Add inserts new pairs [OK]

Common Mistakes:

• Confusing keys with values in output
• Expecting keys printed instead of values
• Thinking indexer causes error if key missing

4. What is wrong with this code snippet?

var dict = new Dictionary<int, string>();
dict.Add(1, "apple");
dict.Add(1, "banana");

medium

A. It will compile and run without errors

B. It causes a runtime exception due to duplicate key

C. It overwrites the first value with the second

D. It causes a compile-time error

Solution

1. Step 1: Understand Add() behavior with duplicate keys

   Adding a key that already exists causes a runtime exception.

2. Step 2: Check code behavior

   Second Add with key 1 throws an ArgumentException at runtime.

3. Final Answer:

   It causes a runtime exception due to duplicate key -> Option B

4. Quick Check:

   Duplicate keys cause runtime error [OK]

Hint: Add() fails if key exists; use indexer to overwrite [OK]

Common Mistakes:

• Assuming Add overwrites existing key
• Expecting compile-time error instead of runtime
• Confusing Add with indexer behavior

5. Given a list of user IDs and names:

var users = new List<(int id, string name)> { (1, "Alice"), (2, "Bob"), (3, "Charlie") };

Which code correctly creates a Dictionary<int, string> mapping IDs to names using a dictionary comprehension style?

hard

A. var dict = users.ToDictionary(u => u.id, u => u.name);

B. var dict = new Dictionary<int, string>(); foreach(var u in users) dict.Add(u.name, u.id);

C. var dict = users.Select(u => new { u.id, u.name }).ToList();

D. var dict = new Dictionary<string, int>(); foreach(var u in users) dict[u.id] = u.name;

Solution

1. Step 1: Understand ToDictionary usage

   ToDictionary converts a list to a dictionary by specifying key and value selectors.

2. Step 2: Check each option

   var dict = users.ToDictionary(u => u.id, u => u.name); correctly maps id to name. var dict = new Dictionary<int, string>(); foreach(var u in users) dict.Add(u.name, u.id); swaps key and value and uses wrong types. var dict = users.Select(u => new { u.id, u.name }).ToList(); creates a list, not dictionary. var dict = new Dictionary<string, int>(); foreach(var u in users) dict[u.id] = u.name; has wrong dictionary types and indexer usage.

3. Final Answer:

   var dict = users.ToDictionary(u => u.id, u => u.name); -> Option A

4. Quick Check:

   ToDictionary creates dictionary from list [OK]

Hint: Use ToDictionary with key and value selectors [OK]

Common Mistakes:

• Swapping key and value in Add
• Using Select instead of ToDictionary
• Mismatching dictionary key-value types