Reject for inverse filtering in Ruby - Time & Space Complexity

Time Complexity: Reject for inverse filtering

O(n)

Understanding Time Complexity

We want to understand how the time needed to run the reject for inverse filtering method changes as the input size grows.

Specifically, how does the number of operations increase when we process more data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def reject_inverse_filtering(data, threshold)
  result = []
  data.each do |value|
    inverse = 1.0 / value
    if inverse > threshold
      result << value
    end
  end
  result
end

This code goes through each number in the data, calculates its inverse, and keeps the original number if the inverse is bigger than a threshold.

Identify Repeating Operations

• Primary operation: Looping through each element in the data array.
• How many times: Once for every element in the input data.

How Execution Grows With Input

As the input data gets bigger, the code does more work by checking each new element once.

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

Pattern observation: The work grows directly in proportion to the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the number of items to check.

Common Mistake

[X] Wrong: "Calculating the inverse inside the loop makes the code slower than linear time."

[OK] Correct: Each inverse calculation is a simple step done once per item, so it still grows linearly with input size.

Interview Connect

Understanding how loops affect time helps you explain your code clearly and shows you can think about efficiency in real tasks.

Self-Check

"What if we added a nested loop inside the existing loop? How would the time complexity change?"