Compact for removing nil values in Ruby - Time & Space Complexity

Time Complexity: Compact for removing nil values

O(n)

Understanding Time Complexity

We want to understand how long it takes to remove nil values from a list using the compact method.

How does the time needed change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

array = [1, nil, 2, nil, 3, nil]
clean_array = array.compact
puts clean_array.inspect

This code removes all nil values from the array and prints the cleaned array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each element in the array to see if it is nil.
• How many times: Once for every element in the array.

How Execution Grows With Input

As the array gets bigger, the method looks at each element one by one.

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

Pattern observation: The number of checks grows directly with the size of the array.

Final Time Complexity

Time Complexity: O(n)

This means the time to remove nil values grows in a straight line as the array gets bigger.

Common Mistake

[X] Wrong: "compact removes nil values instantly, no matter the array size."

[OK] Correct: The method must check each element to know if it is nil, so bigger arrays take more time.

Interview Connect

Understanding how simple methods like compact work helps you explain your code clearly and shows you know how performance changes with data size.

Self-Check

"What if we used a method that removes nil values but also duplicates? How would the time complexity change?"