Pure functions concept in Ruby - Time & Space Complexity

Time Complexity: Pure functions concept

O(n)

Understanding Time Complexity

We want to understand how the time a pure function takes changes as the input size grows.

How does the work inside a pure function scale when given bigger inputs?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def sum_array(arr)
  arr.reduce(0) { |total, num| total + num }
end

numbers = [1, 2, 3, 4, 5]
result = sum_array(numbers)

This code defines a pure function that adds all numbers in an array and returns the total.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each number in the array one by one.
• How many times: Once for each element in the array.

How Execution Grows With Input

As the array gets bigger, the function adds more numbers, so it takes more steps.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: The number of steps grows directly with the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line as the input size grows.

Common Mistake

[X] Wrong: "Pure functions always run instantly no matter the input size."

[OK] Correct: Even pure functions do work on each input item, so bigger inputs take more time.

Interview Connect

Understanding how pure functions scale helps you write clear and predictable code that performs well as data grows.

Self-Check

"What if we changed the function to call itself recursively for each element? How would the time complexity change?"

Practice

1. Which of the following best describes a pure function in Ruby?

easy

A. A function that reads user input and prints output directly.

B. A function that always returns the same output for the same input and has no side effects.

C. A function that modifies global variables to keep track of state.

D. A function that changes the value of its arguments.

Solution

1. Step 1: Understand pure function definition

   A pure function always returns the same result when given the same input and does not affect anything outside itself.

2. Step 2: Compare options to definition

   A function that always returns the same output for the same input and has no side effects. matches this definition exactly. Options A, B, and D involve side effects or changing external state.

3. Final Answer:

   A function that always returns the same output for the same input and has no side effects. -> Option B

4. Quick Check:

   Pure function = consistent output + no side effects [OK]

Hint: Pure functions never change outside data and always return same output [OK]

Common Mistakes:

• Thinking functions that modify variables are pure
• Confusing input/output consistency with side effects
• Assuming printing output is allowed in pure functions

2. Which Ruby function below is a pure function?

easy

A. def add(a, b); a + b; end

B. def add(a, b); puts a + b; end

C. def add(a, b); @sum = a + b; end

D. def add(a, b); print a + b; end

Solution

1. Step 1: Check each function for side effects and output consistency

   def add(a, b); a + b; end returns sum without changing anything outside or printing. def add(a, b); puts a + b; end prints (side effect). def add(a, b); @sum = a + b; end changes instance variable (side effect). def add(a, b); print a + b; end prints (side effect).

2. Step 2: Identify pure function

   Only def add(a, b); a + b; end meets pure function rules: same output for same input, no side effects.

3. Final Answer:

   def add(a, b); a + b; end -> Option A

4. Quick Check:

   Pure function = no side effects + returns value [OK]

Hint: Pure functions return values without printing or changing variables [OK]

Common Mistakes:

• Confusing printing output with returning value
• Assuming modifying instance variables is allowed
• Assuming print doesn't cause side effects

3. What is the output of this Ruby code?

def multiply(x, y)
  x * y
end

result = multiply(3, 4)
puts result

medium

A. Error

B. nil

C. 12

D. 7

Solution

1. Step 1: Understand the multiply function

   The function returns the product of x and y, so multiply(3, 4) returns 12.

2. Step 2: Check the output statement

   puts prints the returned value, so it prints 12.

3. Final Answer:

   12 -> Option C

4. Quick Check:

   multiply(3,4) = 12 [OK]

Hint: Pure functions return predictable output; multiply(3,4) = 12 [OK]

Common Mistakes:

• Thinking function returns nil if no explicit return
• Confusing addition with multiplication
• Expecting error due to missing return keyword

4. Identify the error in this Ruby function that is supposed to be pure:

def increment(n)
  n += 1
  puts n
end

medium

A. It modifies the input variable n.

B. It uses invalid syntax for increment.

C. It does not return any value explicitly.

D. It prints output, causing a side effect.

Solution

1. Step 1: Check for side effects

   The function prints the value of n, which is a side effect because it affects outside world.

2. Step 2: Verify other aspects

   Modifying n locally is allowed; syntax is correct; implicit return is allowed but printing breaks purity.

3. Final Answer:

   It prints output, causing a side effect. -> Option D

4. Quick Check:

   Pure functions must not print or cause side effects [OK]

Hint: Printing inside function breaks purity due to side effects [OK]

Common Mistakes:

• Thinking local variable change breaks purity
• Assuming implicit return is an error
• Ignoring side effects caused by printing

5. You want to write a pure function in Ruby that takes a list of numbers and returns a new list with each number doubled. Which implementation is pure?

hard

A. def double_list(nums)
nums.map { |n| n * 2 }
end

B. def double_list(nums)
nums.collect! { |n| n *= 2 }
nums
end

C. def double_list(nums)
nums.map! { |n| n * 2 }
end

D. def double_list(nums)
nums.clear
nums.push(2, 4, 6)
end

Solution

1. Step 1: Understand pure function requirements

   A pure function returns new data without changing input or external state.

2. Step 2: Analyze each option

   def double_list(nums) nums.collect! { |n| n *= 2 } nums end uses collect! which modifies original array (side effect). def double_list(nums) nums.map { |n| n * 2 } end returns a new array with doubled values without changing original. def double_list(nums) nums.map! { |n| n * 2 } end uses map! which modifies original array (side effect). def double_list(nums) nums.clear nums.push(2, 4, 6) end clears and modifies original array (side effect).

3. Final Answer:

   def double_list(nums) nums.map { |n| n * 2 } end -> Option A

4. Quick Check:

   Pure function = no input change + returns new data [OK]

Hint: Use non-destructive methods like map, avoid modifying input [OK]

Common Mistakes:

• Using destructive methods like map! or clear
• Modifying input array instead of returning new one
• Confusing each with map for transformation