Array methods (length, include?, flatten) in Ruby - Time & Space Complexity

Time Complexity: Array methods (length, include?, flatten)

O(1) for length, O(n) for include? and flatten

Understanding Time Complexity

When using array methods like length, include?, and flatten, it helps to know how their speed changes as the array grows.

We want to find out how many steps these methods take when the array gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

arr = [1, 2, [3, 4], 5]
size = arr.length
has_three = arr.include?(3)
flat = arr.flatten
puts size, has_three, flat.inspect

This code gets the size of the array, checks if 3 is inside, and then flattens nested arrays into one.

Identify Repeating Operations

Look at what repeats or loops inside these methods.

• Primary operation: include? and flatten both check elements one by one.
• How many times: include? checks each element until it finds a match or reaches the end. flatten visits every element, including inside nested arrays.
• length: Just returns a stored number, no loops.

How Execution Grows With Input

As the array gets bigger, the work done changes differently for each method.

Input Size (n)	Approx. Operations for include?	Approx. Operations for flatten	Approx. Operations for length
10	Up to 10 checks	Visit all 10 elements (including nested)	1 (direct)
100	Up to 100 checks	Visit all 100 elements (including nested)	1 (direct)
1000	Up to 1000 checks	Visit all 1000 elements (including nested)	1 (direct)

Pattern observation: include? and flatten take more steps as the array grows, while length stays quick.

Final Time Complexity

Time Complexity: O(1) for length, O(n) for include? and flatten

This means length is very fast no matter the size, but include? and flatten take longer as the array grows.

Common Mistake

[X] Wrong: "length must count all elements every time, so it's slow like include?."

[OK] Correct: Ruby stores the array size, so length just returns that number instantly without counting.

Interview Connect

Knowing how common array methods work under the hood helps you write faster code and explain your choices clearly in interviews.

Self-Check

"What if the array contains deeply nested arrays? How would that affect the time complexity of flatten?"