When writing code, it is important to understand how fast it works and how much resources it consumes. Programmers use the concept of algorithm complexity to measure this. In this article, you’ll learn the basics of algorithm complexity with simple examples in Ruby.

What is Algorithm Complexity?

Algorithm complexity describes how the execution time or memory usage of an algorithm changes depending on the size of the input data.

For example, a list with 10 elements may process quickly, but what happens if the list grows to 10,000 elements?

Complexity is often represented using Big O notation. Here are the most common types of complexity:

  • ( O(1) ) — Constant
  • ( O(n) ) — Linear
  • ( O(n^2) ) — Quadratic
  • ( O(\log n) ) — Logarithmic

Examples of Complexity in Ruby

( O(1) ): Constant Complexity

An algorithm with constant complexity executes in the same amount of time regardless of the size of the input data.

def get_first_element(array)
  array[0]
end

numbers = [1, 2, 3, 4, 5]
puts get_first_element(numbers) # Always returns the first element

Why ( O(1) )? The function always performs one operation: it simply retrieves the first element. The array size does not affect the speed.

( O(n) ): Linear Complexity

An algorithm with linear complexity processes each element of the input data.

def print_all_elements(array)
  array.each { |element| puts element }
end

numbers = [1, 2, 3, 4, 5]
print_all_elements(numbers) # Prints each element of the array

Why ( O(n) )? The more elements in the array, the more operations are performed.

( O(n^2) ): Quadratic Complexity

An algorithm with quadratic complexity uses nested loops.

def print_all_pairs(array)
  array.each do |x|
    array.each do |y|
      puts "(#{x}, #{y})"
    end
  end
end

numbers = [1, 2, 3]
print_all_pairs(numbers)

Why ( O(n^2) )? For each element, another full loop runs. If the array has 3 elements, there will be 3 × 3 = 9 operations.

( O(log n) ): Logarithmic Complexity

Algorithms with logarithmic complexity often appear in search tasks. For example, binary search:

def binary_search(array, target)
  low = 0
  high = array.size - 1

  while low <= high
    mid = (low + high) / 2
    if array[mid] == target
      return mid
    elsif array[mid] < target
      low = mid + 1
    else
      high = mid - 1
    end
  end

  nil
end

numbers = [1, 3, 5, 7, 9, 11]
puts binary_search(numbers, 5) # Finds element 5

Why ( O(log n) )? With each step, the algorithm halves the size of the array it needs to search. If the array contains 16 elements, it takes only 4 steps to find the desired element.

How to Determine Complexity?

To determine the complexity of an algorithm, follow these steps:

  1. Identify the most “expensive” loops or operations.
  2. Count how many times they execute.
  3. Express the result in terms of ( n ), the size of the input data.

Conclusion

Understanding algorithm complexity helps write code that is fast and efficient. Here are the key takeaways:

  • Avoid unnecessary nested loops — quadratic complexity can be very slow.
  • Look for optimal solutions — for instance, use binary search instead of a full scan.
  • Practice! The more you analyze code, the easier it will be to understand its complexity.

Start with simple algorithms and try to determine their complexity! 🚀