Array Access and Update at Index in DSA C++ - Time & Space Complexity

Time Complexity: Array Access and Update at Index

O(1)

Understanding Time Complexity

We want to understand how fast we can get or change a value in an array by its position.

The question is: how does the time to access or update an element change as the array grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int arr[1000];
int index = 500;

// Access element at index
int value = arr[index];

// Update element at index
arr[index] = 42;

This code accesses and updates the element at a specific position in the array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Direct access to an array element by index.
• How many times: Each access or update happens once per operation.

How Execution Grows With Input

Accessing or updating an element takes the same time no matter how big the array is.

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

Pattern observation: The time stays constant even as the array size grows.

Final Time Complexity

Time Complexity: O(1)

This means accessing or updating an element by index takes the same short time no matter how big the array is.

Common Mistake

[X] Wrong: "Accessing an element takes longer if the array is bigger because it has to look through all elements."

[OK] Correct: Arrays allow direct access by position, so the computer jumps straight to the spot without checking others.

Interview Connect

Knowing that array access and update are very fast helps you choose the right data structure and explain your choices clearly in interviews.

Self-Check

"What if we used a linked list instead of an array? How would the time complexity for access and update change?"

Practice

1. What does the expression arr[2] do in an array named arr?

easy

A. Accesses the element at index 2 of the array

B. Accesses the element at index 0 of the array

C. Updates the element at index 2 to zero

D. Deletes the element at index 2

Solution

1. Step 1: Understand array indexing

   Arrays use zero-based indexing, so arr[2] refers to the third element.

2. Step 2: Identify the operation

   The expression arr[2] accesses (reads) the element at index 2 without changing it.

3. Final Answer:

   Accesses the element at index 2 of the array -> Option A

4. Quick Check:

   arr[2] means read element at index 2 [OK]

Hint: Remember arrays start at index 0, so arr[2] is third element [OK]

Common Mistakes:

• Thinking arr[2] updates the element
• Confusing index 2 with index 0
• Assuming arr[2] deletes an element

2. Which of the following is the correct syntax to update the 4th element of an integer array nums to 10 in C++?

easy

A. nums(4) = 10;

B. nums[3] = 10;

C. nums[4] == 10;

D. nums{3} = 10;

Solution

1. Step 1: Recall zero-based indexing

   The 4th element is at index 3 because counting starts from 0.

2. Step 2: Check correct syntax for assignment

   Use square brackets for indexing and single equals sign for assignment: nums[3] = 10;.

3. Final Answer:

   nums[3] = 10; -> Option B

4. Quick Check:

   Use nums[3] = 10; to update 4th element [OK]

Hint: Use square brackets and single = to update array element [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Using double equals (==) instead of single equals (=)
• Using curly braces for indexing

3. What will be the output of the following C++ code?

int arr[5] = {1, 2, 3, 4, 5};
arr[1] = arr[3] + 2;
std::cout << arr[1];

medium

A. 6

B. 4

C. 2

D. 5

Solution

1. Step 1: Identify initial array values

   arr = [1, 2, 3, 4, 5]

2. Step 2: Calculate new value for arr[1]

   arr[3] is 4, so arr[1] = 4 + 2 = 6

3. Step 3: Output the updated arr[1]

   std::cout prints 6

4. Final Answer:

   6 -> Option A

5. Quick Check:

   arr[1] = arr[3] + 2 = 6 [OK]

Hint: Remember arr[3] is 4, so arr[1] becomes 6 [OK]

Common Mistakes:

• Confusing arr[1] and arr[3] values
• Forgetting to add 2
• Printing old value of arr[1]

4. Find the error in the following code snippet that tries to update the 2nd element of array data to 100:

int data[3] = {10, 20, 30};
data(1) = 100;

medium

A. Cannot assign integer to array element

B. Array size is too small

C. Using parentheses instead of square brackets for indexing

D. Missing semicolon after array declaration

Solution

1. Step 1: Check array indexing syntax

   Arrays use square brackets [] for indexing, not parentheses ().

2. Step 2: Identify the incorrect line

   data(1) = 100; is invalid syntax; correct is data[1] = 100;.

3. Final Answer:

   Using parentheses instead of square brackets for indexing -> Option C

4. Quick Check:

   Use square brackets [] to access array elements [OK]

Hint: Use [] for array access, not () [OK]

Common Mistakes:

• Using parentheses for indexing
• Assuming array size is wrong
• Missing semicolon errors

5. Given an array int scores[5] = {10, 20, 30, 40, 50};, which code snippet correctly doubles the value at index 2 and then updates index 4 to be the sum of the new index 2 value and index 0 value?

hard

A. scores[2] *= 2;
scores[4] = scores[4] + scores[0];

B. scores[2] = scores[2] * 2;
scores[4] = scores[2] + scores[4];

C. scores[2] = scores[2] * scores[2];
scores[4] = scores[0] + scores[2];

D. scores[2] *= 2;
scores[4] = scores[0] + scores[2];

Solution

1. Step 1: Initial array

   scores = [10, 20, 30, 40, 50]

2. Step 2: Double index 2

   scores[2] = 30 * 2 = 60

3. Step 3: Update index 4

   scores[4] = 60 + 10 = 70

4. Step 4: Trace options

   • Snippet with *= 2 then [4] = [4] + [0]: [2]=60, [4]=50+10=60 (wrong)
   • Snippet with *= 2 then [4] = [0] + [2]: [2]=60, [4]=10+60=70 (correct)
   • Snippet with [2] = [2] * [2] then [4] = [0] + [2]: [2]=900, [4]=910 (wrong)
   • Snippet with [2] = [2] * 2 then [4] = [2] + [4]: [2]=60, [4]=60+50=110 (wrong)

5. Final Answer:

   scores[2] *= 2; scores[4] = scores[0] + scores[2]; -> Option D

6. Quick Check:

   scores[2] *= 2 (60); scores[4] = 10 + 60 (70) [OK]

Hint: Verify doubling uses *2 or equivalent, sum uses new [2] + [0] exactly [OK]

Common Mistakes:

• Adding to old index 4 value
• Squaring index 2 instead of doubling
• Summing new index 2 with index 4