Adding and updating values in Go - Time & Space Complexity

Time Complexity: Adding and updating values

O(1)

Understanding Time Complexity

When we add or update values in a data structure, it is important to know how the time it takes changes as the data grows.

We want to understand how the work needed grows when we add or change values.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func addOrUpdate(m map[string]int, key string, value int) {
    m[key] = value
}

This code adds a new key with a value or updates the value if the key already exists in the map.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting or updating a key in the map.
• How many times: This operation happens once per call.

How Execution Grows With Input

Adding or updating a value in a map usually takes about the same time no matter how many items are in the map.

Input Size (n)	Approx. Operations
10	About 1 operation
100	About 1 operation
1000	About 1 operation

Pattern observation: The time to add or update stays roughly the same even as the map grows larger.

Final Time Complexity

Time Complexity: O(1)

This means adding or updating a value takes about the same short time no matter how many items are already stored.

Common Mistake

[X] Wrong: "Adding a value takes longer as the map gets bigger because it has to check all keys."

[OK] Correct: Maps use a special way to find keys quickly, so they do not check every key one by one.

Interview Connect

Understanding how adding and updating values works helps you explain how data structures keep things fast and efficient in real programs.

Self-Check

"What if we changed the map to a list and added or updated values there? How would the time complexity change?"

Practice

1. What happens when you assign a value to a new key in a Go map using mapName[key] = value?

easy

A. A new key-value pair is added to the map.

B. The map is deleted.

C. The map becomes empty.

D. The program crashes.

Solution

1. Step 1: Understand map assignment

   Assigning a value to a new key in a map adds that key with the value.

2. Step 2: Differentiate from update

   If the key exists, the value updates; if not, a new pair is created.

3. Final Answer:

   A new key-value pair is added to the map. -> Option A

4. Quick Check:

   Adding new key = new pair added [OK]

Hint: Assigning to new key adds pair, not error or delete [OK]

Common Mistakes:

• Thinking map clears on new key assignment
• Confusing adding with deleting
• Assuming program crashes on new key

2. Which of the following is the correct syntax to update the value for key "age" to 30 in a Go map named person?

easy

A. person["age"] := 30

B. person["age"] = 30

C. person.age = 30

D. person.update("age", 30)

Solution

1. Step 1: Recall map update syntax

   In Go, map values are updated by assigning with = operator: map[key] = value.

2. Step 2: Check each option

   person["age"] = 30 uses correct syntax. person["age"] := 30 uses := which is for variable declaration, not map update. person.age = 30 uses dot notation which is invalid for maps. person.update("age", 30) uses a method that does not exist.

3. Final Answer:

   person["age"] = 30 -> Option B

4. Quick Check:

   Use = to update map value [OK]

Hint: Use =, not := or dot, to update map values [OK]

Common Mistakes:

• Using := instead of = for map update
• Using dot notation for map keys
• Trying to call update method on map

3. What is the output of this Go code?

m := map[string]int{"a": 1, "b": 2}
m["a"] = 5
fmt.Println(m["a"])

medium

A. 1

B. 2

C. 5

D. 0

Solution

1. Step 1: Analyze initial map values

   The map m starts with keys "a":1 and "b":2.

2. Step 2: Update value for key "a"

   m["a"] = 5 changes the value for "a" from 1 to 5.

3. Step 3: Print updated value

   fmt.Println(m["a"]) prints the updated value 5.

4. Final Answer:

   5 -> Option C

5. Quick Check:

   Updated value prints 5 [OK]

Hint: Updated map key prints new value, not old [OK]

Common Mistakes:

• Expecting old value instead of updated
• Confusing key "b" value with "a"
• Thinking print shows zero value

4. Identify the error in this Go code snippet that tries to add a new key-value pair to a map:

var m map[string]int
m["new"] = 10

medium

A. Key "new" is a reserved word and cannot be used.

B. Syntax error: missing semicolon after map declaration.

C. Value 10 must be a string, not int.

D. Map m is nil and not initialized before adding a key.

Solution

1. Step 1: Understand map initialization

   Declaring var m map[string]int creates a nil map. It must be initialized with make() before adding keys.

2. Step 2: Identify error cause

   Assigning m["new"] = 10 on a nil map causes runtime panic because map is not initialized.

3. Final Answer:

   Map m is nil and not initialized before adding a key. -> Option D

4. Quick Check:

   Maps must be initialized before adding keys [OK]

Hint: Always initialize maps with make() before adding keys [OK]

Common Mistakes:

• Assuming var declares initialized map
• Thinking key "new" is invalid
• Confusing value types for map

5. Given a map inventory := map[string]int{"apple": 5, "banana": 3}, write the correct Go code to add 2 more apples to the inventory without overwriting the existing count.

hard

A. inventory["apple"] += 2

B. inventory["apple"] = inventory["apple"] - 2

C. inventory["apple"] = 2

D. inventory.add("apple", 2)

Solution

1. Step 1: Understand current value

   Current count for "apple" is 5 in the map.

2. Step 2: Add 2 without overwriting

   Use += operator to add 2 to existing value: inventory["apple"] += 2.

3. Step 3: Check other options

   inventory["apple"] = 2 overwrites with 2, not add. inventory["apple"] = inventory["apple"] - 2 subtracts 2. inventory.add("apple", 2) uses a non-existent method.

4. Final Answer:

   inventory["apple"] += 2 -> Option A

5. Quick Check:

   Use += to add to map value [OK]

Hint: Use += to add to existing map value, not = [OK]

Common Mistakes:

• Overwriting value instead of adding
• Subtracting instead of adding
• Using non-existent map methods