Array operations and their complexities in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the time complexity of accessing an element by index in an array?

Accessing an element by its index in an array takes constant time, O(1), because arrays allow direct access to any element using its position.

intermediate

Why does inserting an element at the end of a dynamic array sometimes take more than O(1) time?

Inserting at the end is usually O(1), but when the array is full, it needs to resize (allocate a bigger array and copy elements), which takes O(n) time. This resizing happens occasionally, so average insertion is still O(1) amortized.

beginner

What is the time complexity of inserting an element at the beginning of an array?

Inserting at the beginning requires shifting all existing elements one position to the right, so it takes O(n) time, where n is the number of elements in the array.

beginner

Explain the time complexity of deleting an element from the middle of an array.

Deleting an element from the middle requires shifting all elements after it one position to the left to fill the gap. This shifting takes O(n) time, where n is the number of elements in the array.

intermediate

What is the difference between worst-case and amortized time complexity in array operations?

Worst-case time complexity is the maximum time an operation can take (e.g., resizing an array during insertion). Amortized time averages the cost over many operations, showing that occasional expensive operations don't affect the average much.

What is the time complexity of accessing the 5th element in an array?

A O(1)

B O(n)

C O(log n)

D O(n^2)

Accessing any element by index in an array is done in constant time, O(1).

Which operation on an array typically requires O(n) time?

A Accessing an element by index

B Accessing the last element

C Inserting at the end (when no resize needed)

D Inserting at the beginning

Inserting at the beginning requires shifting all elements, which takes O(n) time.

Why does resizing a dynamic array take O(n) time?

A Because it needs to copy all existing elements to a new larger array

B Because it deletes all elements

C Because it sorts the array

D Because it accesses elements randomly

Resizing involves copying all elements to a new array, which takes O(n) time.

What is the amortized time complexity of inserting elements at the end of a dynamic array?

A O(n)

B O(1)

C O(n^2)

D O(log n)

Although resizing is costly, it happens rarely, so average insertion time is O(1) amortized.

Deleting an element from the middle of an array requires:

A No shifting of elements

B Shifting elements to the right

C Shifting elements to the left

D Sorting the array

Elements after the deleted one must be shifted left to fill the gap.

Describe the time complexities of accessing, inserting, and deleting elements in an array.

Think about how many elements need to be moved for each operation.

Explain why dynamic arrays sometimes need resizing and how it affects operation time.

Consider what happens when you add more elements than the current space.

Practice

1. Which array operation generally has the fastest time complexity?

easy

A. Accessing an element by its index

B. Inserting an element at the beginning

C. Deleting an element from the middle

D. Searching for an element by value

Solution

1. Step 1: Understand array indexing

   Arrays allow direct access to elements by their position (index) in constant time.

2. Step 2: Compare with other operations

   Inserting or deleting elements requires shifting other elements, which takes more time.

3. Final Answer:

   Accessing an element by its index -> Option A

4. Quick Check:

   Access by index = O(1) [OK]

Hint: Access by index is always fastest in arrays [OK]

Common Mistakes:

• Thinking insertion at start is fast
• Confusing search with access
• Assuming deletion is constant time

2. Which of the following is the correct way to insert an element x at index 2 in an array arr in Python?

easy

A. arr.insert(2, x)

B. arr.add(2, x)

C. arr.push(2, x)

D. arr.append(2, x)

Solution

1. Step 1: Recall Python list insertion method

   Python lists use insert(index, value) to add elements at a specific position.

2. Step 2: Check other options

   add and push are not valid list methods; append adds only at the end.

3. Final Answer:

   arr.insert(2, x) -> Option A

4. Quick Check:

   Use insert(index, value) to add at position [OK]

Hint: Use insert() to add at any index in Python lists [OK]

Common Mistakes:

• Using append() to insert at middle
• Confusing insert() with add() or push()
• Wrong method names for Python lists

3. Consider this Python code:

arr = [10, 20, 30, 40, 50]
arr.pop(1)
print(arr)

What will be the output?

medium

A. [20, 30, 40, 50]

B. [10, 30, 40, 50]

C. [10, 20, 40, 50]

D. [10, 20, 30, 40]

Solution

1. Step 1: Understand pop(index) behavior

   The pop(1) removes the element at index 1, which is 20.

2. Step 2: Remove element and print array

   After removal, the array becomes [10, 30, 40, 50].

3. Final Answer:

   [10, 30, 40, 50] -> Option B

4. Quick Check:

   pop(1) removes second element [OK]

Hint: pop(index) removes element at that index [OK]

Common Mistakes:

• Removing wrong element index
• Confusing pop() with remove(value)
• Expecting original array unchanged

4. The following code tries to insert an element at index 5 in an array of length 4:

arr = [1, 2, 3, 4]
arr.insert(5, 10)
print(arr)

What is the output?

medium

A. [10, 1, 2, 3, 4]

B. IndexError: list index out of range

C. [1, 2, 3, 4, 10]

D. [1, 2, 3, 10, 4]

Solution

1. Step 1: Check insert behavior with index beyond length

   Python's insert places the element at the end if index is greater than list length.

2. Step 2: Insert 10 at the end and print

   The array becomes [1, 2, 3, 4, 10]. No error occurs.

3. Final Answer:

   [1, 2, 3, 4, 10] -> Option C

4. Quick Check:

   Insert beyond length appends at end [OK]

Hint: Insert beyond length adds element at end [OK]

Common Mistakes:

• Expecting IndexError
• Inserting element in wrong position
• Confusing insert with assignment

5. You have a large array and need to frequently add and remove elements at the start. Which data structure is better for this use case to improve performance?

hard

A. Queue implemented with array

B. Array

C. Stack

D. Linked list

Solution

1. Step 1: Analyze array performance for start operations

   Arrays require shifting all elements when adding/removing at the start, which is slow (O(n)).

2. Step 2: Consider linked list advantages

   Linked lists allow fast insertions and deletions at the start (O(1)) without shifting elements.

3. Step 3: Evaluate other options

   Stacks and queues implemented with arrays still face shifting issues for start operations.

4. Final Answer:

   Linked list -> Option D

5. Quick Check:

   Linked list = fast start insert/delete [OK]

Hint: Use linked list for fast start insert/delete [OK]

Common Mistakes:

• Choosing array despite slow start operations
• Confusing stack/queue with linked list
• Ignoring shifting cost in arrays