Array operations and their complexities in Data Structures Theory - Time & Space Complexity

Time Complexity: Array operations and their complexities

O(1) for access and append, O(n) for search, insert at start, and delete

Understanding Time Complexity

Arrays are one of the most common data structures. Knowing how fast different operations run helps us choose the right approach.

We want to understand how the time to do things like access, search, insert, or delete changes as the array grows.

Scenario Under Consideration

Analyze the time complexity of the following array operations.

// Access element at index i
value = array[i]

// Search for a value
for element in array:
    if element == target:
        return True

// Insert at end
array.append(new_value)

// Insert at start
array.insert(0, new_value)

// Delete element at index i
array.pop(i)
    

This code shows common array operations: accessing, searching, inserting, and deleting elements.

Identify Repeating Operations

Look at what repeats and what runs once.

• Primary operation: Looping through the array to search for a value.
• How many times: Up to n times, where n is the number of elements.

Access, append, insert at start, and pop have different costs, but only search uses a loop over the array.

How Execution Grows With Input

As the array gets bigger, some operations take longer, others stay quick.

Input Size (n)	Approx. Operations
10	Access: 1, Search: up to 10, Append: 1, Insert start: 10, Delete at i: 10
100	Access: 1, Search: up to 100, Append: 1, Insert start: 100, Delete at i: 100
1000	Access: 1, Search: up to 1000, Append: 1, Insert start: 1000, Delete at i: 1000

Access and append stay fast no matter the size. Search, insert at start, and delete take longer as the array grows.

Final Time Complexity

Time Complexity: O(1) for access and append, O(n) for search, insert at start, and delete

This means accessing or adding at the end is quick and does not slow down with size, but searching or changing elements inside can take longer as the array grows.

Common Mistake

[X] Wrong: "Searching an array is always fast because computers are quick."

[OK] Correct: Even if computers are fast, searching means checking each element one by one, so it takes longer as the array grows.

Interview Connect

Understanding these time costs helps you explain your choices clearly and shows you know how data size affects performance, a key skill in real projects.

Self-Check

"What if the array was sorted? How would that change the time complexity of searching for a value?"