Dictionary methods and access patterns in C Sharp (C#) - Time & Space Complexity

Time Complexity: Dictionary methods and access patterns

O(n)

Understanding Time Complexity

When we use dictionaries in C#, it is important to know how fast we can find, add, or remove items.

We want to understand how the time to do these actions changes as the dictionary grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

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

This code adds n items to a dictionary and then accesses each item by its key.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding and accessing items in the dictionary inside loops.
• How many times: Each operation happens n times, once per loop iteration.

How Execution Grows With Input

Each add or access takes about the same time, no matter how big the dictionary is.

Input Size (n)	Approx. Operations
10	About 10 adds + 10 accesses = 20 operations
100	About 100 adds + 100 accesses = 200 operations
1000	About 1000 adds + 1000 accesses = 2000 operations

Pattern observation: The total work grows directly with n, doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the total time grows in a straight line with the number of items added and accessed.

Common Mistake

[X] Wrong: "Accessing dictionary items takes longer as the dictionary gets bigger because it searches through all items."

[OK] Correct: Dictionaries use a special method to find items quickly, so access time stays about the same no matter the size.

Interview Connect

Knowing how dictionary operations scale helps you write fast and efficient code, a skill valued in many programming tasks.

Self-Check

"What if we used a list instead of a dictionary for storing and accessing items by key? How would the time complexity change?"

Practice

1. What does the ContainsKey method do in a C# Dictionary?

easy

A. Checks if a specific key exists in the dictionary

B. Adds a new key-value pair to the dictionary

C. Removes a key and its value from the dictionary

D. Returns the number of items in the dictionary

Solution

1. Step 1: Understand the purpose of ContainsKey

   The ContainsKey method checks if a given key is present in the dictionary.

2. Step 2: Compare with other dictionary methods

   Add adds items, Remove deletes items, and Count returns the number of items, so these are different from ContainsKey.

3. Final Answer:

   Checks if a specific key exists in the dictionary -> Option A

4. Quick Check:

   ContainsKey checks key presence [OK]

Hint: ContainsKey checks if key exists before access [OK]

Common Mistakes:

• Confusing ContainsKey with Add method
• Thinking ContainsKey returns a value instead of a boolean
• Mixing ContainsKey with Count property

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

easy

A. ages.Add("Alice", 30);

B. ages.Add["Alice"] = 30;

C. ages["Alice"].Add(30);

D. ages.Insert("Alice", 30);

Solution

1. Step 1: Recall the syntax for adding items to Dictionary

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

2. Step 2: Check each option's syntax

   ages.Add("Alice", 30); uses Add("Alice", 30) which is correct. ages.Add["Alice"] = 30; uses square brackets with Add which is invalid. ages["Alice"].Add(30); tries to call Add on the value, which is wrong. ages.Insert("Alice", 30); uses Insert which does not exist for Dictionary.

3. Final Answer:

   ages.Add("Alice", 30); -> Option A

4. Quick Check:

   Add(key, value) syntax [OK]

Hint: Use Add(key, value) to insert new pairs [OK]

Common Mistakes:

• Using square brackets with Add method
• Trying to call Add on a value instead of dictionary
• Using Insert method which does not exist

3. What will be the output of this code?

var dict = new Dictionary<string, int>();
dict.Add("x", 10);
dict["y"] = 20;
Console.WriteLine(dict["x"] + dict["y"]);

medium

A. 10 20

B. 30

C. x y

D. Runtime error

Solution

1. Step 1: Understand dictionary additions

   First, dict.Add("x", 10) adds key "x" with value 10. Then dict["y"] = 20 adds key "y" with value 20.

2. Step 2: Calculate the sum printed

   dict["x"] is 10 and dict["y"] is 20, so their sum is 30.

3. Final Answer:

   30 -> Option B

4. Quick Check:

   10 + 20 = 30 [OK]

Hint: Sum values accessed by keys with dict[key] syntax [OK]

Common Mistakes:

• Expecting output as separate values instead of sum
• Confusing keys and values in output
• Thinking dict["y"] is invalid without Add

4. Identify the error in this code snippet:

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

medium

A. Key "a" will be removed automatically

B. Compilation error due to missing semicolon

C. Duplicate key exception on second Add call

D. Output will be 2 without error

Solution

1. Step 1: Understand Add method behavior with duplicate keys

   The Add method throws an exception if the key already exists.

2. Step 2: Analyze the code flow

   The first Add("a", 1) works fine. The second Add("a", 2) tries to add the same key again, causing an exception.

3. Final Answer:

   Duplicate key exception on second Add call -> Option C

4. Quick Check:

   Adding duplicate key throws exception [OK]

Hint: Add throws error if key exists; use indexer to overwrite [OK]

Common Mistakes:

• Assuming Add overwrites existing keys
• Expecting no error and value updated
• Confusing Add with indexer assignment

5. Given a dictionary scores with student names as keys and their scores as values, which code snippet safely retrieves the score for "John" without causing an error if the key is missing?

hard

A. int score = scores.ContainsKey("John");

B. int score = scores.GetValueOrDefault("John");

C. int score = scores["John"];

D. scores.TryGetValue("John", out int score);

Solution

1. Step 1: Understand safe retrieval methods

   Using TryGetValue safely tries to get the value and returns false if key is missing without error.

2. Step 2: Analyze each option

   int score = scores["John"]; throws an exception if "John" is missing. int score = scores.GetValueOrDefault("John"); is invalid in C# Dictionary (GetValueOrDefault is not standard). scores.TryGetValue("John", out int score); uses TryGetValue correctly. int score = scores.ContainsKey("John"); returns a boolean, not the score.

3. Final Answer:

   scores.TryGetValue("John", out int score); -> Option D

4. Quick Check:

   TryGetValue safely gets value [OK]

Hint: Use TryGetValue to avoid errors on missing keys [OK]

Common Mistakes:

• Using indexer without checking key existence
• Confusing ContainsKey with value retrieval
• Expecting GetValueOrDefault method on Dictionary