Complexity Analysis and Optimization in Ruby | CodeSignal Learn

Complexity Analysis and Optimization in Ruby | CodeSignal Learn

Introduction

Welcome to the lesson! Today, our journey will ride through the captivating world of Complexity Analysis and techniques for optimization. These fundamental concepts are crucial for every programmer, especially those seeking to build efficient and scalable programs. Having a firm understanding of how code impacts system resources enables us to optimize it for better performance. Isn't it fascinating how we can tailor our code to be more efficient? So, buckle up and let's get started!

Remind Complexity Analysis

First things first, let's remind ourselves of what Complexity Analysis is. Simply put, Complexity Analysis is a way of determining how our data input size affects the performance of our program, most commonly in terms of time and space. In more technical terms, it’s a theoretical measure of the execution of an algorithm, particularly the time or memory needed, given the problem size n, which is usually the number of items. Are you interested in how it works? Let's take, for example, a linear search function that looks for a value x in an array of size n . In the worst-case scenario, the function has to traverse through the entire array, thus taking time proportional to n . We would say that this function has a time complexity of O(n) . Ruby def linear_search(x, lst) lst.each_with_index do |item, i| return i if item == x end -1 end # Use the linear-search function index = linear_search(5, [1, 2, 3, 4, 5, 6, 7, 8, 9]) # index becomes 4

Understanding O(1), O(n), and O(n log n)

O(1)

Basic Examples of Optimization

O(n)

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Next, let's explore a more complex optimization example with a function that checks for duplicate numbers in a list. Here's the initial version of such a function, which uses two loops:

Ruby

def contains_duplicate(lst)
  lst.each_with_index do |item, i|
    (i + 1...lst.length).each do |j|
      return true if item == lst[j]
    end
  end
  false
end

This function checks every pair of numbers, resulting in a time complexity of O(n²). Here's why: for every element in the list, it compares it with almost every other element. So, the number of operations grows quadratically with n, hence the complexity O(n²).

However, we can optimize this function by sorting the list first and just checking the elements next to each other:

Ruby

def contains_duplicate(lst)
  lst.sort!
  lst.each_cons(2) do |a, b|
    return true if a == b
  end
  false
end

Now, even including the time it takes to sort the list (usually $O(n \log n)$ ), this updated function is more efficient. After sorting, we only make a single pass through the list — an $O(n)$ operation. But since $O(n \log n)$ is more significant than $O(n)$ for large n, the overall time complexity is $O(n \log n)$ .