Big O explained, ruby examples

Big O

The Big O is a notation used in computer science to describe the complexity of an algorithm. For example, it is used to measure an algorithm’s time and space complexity, the amount of time and memory it takes to execute. In addition, the Big O notation is used to compare different algorithms’ efficiency and determine the most efficient.

The Big O notation doesn’t say the algorithm’s speed in seconds.

Big O types with examples

1. O(1)
2. O(log n)
3. O(n)
4. O(n log(n))
5. O(n^2)
6. O(2^n)
7. O(n!)

1. O(1)

Constant and no loops.

Example:

def print
  str = 'Hello O(1)' # O(1)
  p str              # O(1)
end

Since there are no loops in this method, it is an O(1) method. To be more precise, it’s O(1+1) since we have two lines in the method, but even so, we say O(1) because any extra (+1) doesn’t matter in terms of scalability.

2. O(log n)

Logarithmic, usually a search algorithm, and has log n if arrays are sorted (binary search).

This means that time grows linearly while (n) grows exponentially. Thus, if it takes (1) seconds to calculate (10) items, it will take (2) seconds to compute (100) items, (3) seconds to compute (1000) items, and so on.

Example:

def log(n)
  return 0 if n - 1 == 0

  log(n / 2) + 1
end

This recursive method finds x from the following formula 2^x=n or 2^x=8.

log(8) # the method will return 3
log(8) -> 8 / 2 = 4 # first iteration
log(4) -> 2 / 2 = 2 # second iteration
log(2) -> 2 / 2 = 1 # third iteration
log(1) -> return    # last iteration

So the log(n) method is 3 levels deep when n is 8 and 4 levels deep when n is 16, 5 levels deep for n is equal to 32.

3. O(n)

Linear, usually loops, while loops through n elements.

Example:

array = [1,2,3,4,5]
def print(array)
  array.each { |elm| p elm } # O(n)
end

We’re iterating over an array of elements, which means we’re printing every n element of the given array.

4. O(n log(n))

Log-linear, usually sorting operations such as merge sort algorithm.

Example:

def n_log_n(n)
  i = 1
  while i <= n
    j = 1
    while j < n
      p "i: #{i}, j: #{j}"
      j *= 2
    end
    i += 1
  end
end

The running time grows proportionally to n log n input data. For example, if n is 16, this algorithm will run 16 * log(16) = 16 * 4 = 64 times.

5. O(n^2)

Quadratic, where each element in the collection must be compared with every other part - two nested loops.

Example:

array = [1,2,3,4,5]
def sum_pairs(array)
  array.each do |i|          # O(n)
    array.each { |j| p i+j } # nested O(n)
  end
end

6. O(2^n)

An exponential, recursive algorithm that solves a problem of size N.

Example:

def fibonacci(n)
  return n if n < 2

  return fibonacci(n-1) + fibonacci(n-2)
end

I think the Fibonacci method is an excellent example of O(2^n).

7. O(n!)

Factorial, you add a loop for each element. This is the most expensive operation!!!

Example:

def factorial(n)
  Array(0..n).each do |i| # O(n!)
    p n
    factorial(i-1)
  end
end

Computing Big O - “Rules”

1. In Big O, we always show the worst case When we calculate big O, we always think of the worst case.

array = [0,0,1,0,0]
def find_one(array)
  array.find_by { |i| i == 1 } # still O(n)
end

Even though the find_by method will not iterate through all the elements for the given array because the 1 we are looking for is right in the middle of the collection. The find_by method will return it as soon as it finds it, we must take into account that 1 can be at the end of the [0,0,0,0,1] array, and this is our worst case. So, we still need to loop through all the elements in this case.

2. We need to remove all constants.

array = [0,0,1,0,0]
def find_one_and_print(array)
  num = array.find_by { |i| i == 1 } # O(n)
  p num                              # O(1)
end

The Big O calculation for the above function is O(n+1), but since +1 is not significant, we want to remove the constant +1 so that it becomes just O(n).

Even for the following function:

array = [0,0,1,0,0]
def find_one_and_print(array)
  one = array.find_by { |i| i == 1 }  # O(n)
  zero = array.find_by { |i| i == 0 } # O(n)
  p one                               # O(1)
  p zero                              # O(1)
end

The calculation is O(2n+1+1), but the most significant part is still (n)`, so we remove all constants O(2n+1+1) = O(n)

3. Different inputs must have other O(a+b) variables.

array1 = [0,0,1,0,0]
array2 = [0,0,0,0,1]
def find_one_and_print(array1, array2)
  num1 = array1.find_by { |i| i == 1 } # O(a) -> not O(n)
  num2 = array2.find_by { |i| i == 1 } # O(b) -> not O(n)
end

Since we now have two arrays passed as method arguments, we need to name them differently to distinguish between them. So for array1, we use variable a. For array2, we use variable b. The calculation will be O(a+b).

4. Drop Non-dominant terms

array = [1,2,3,4,5]
def sum_pairs(array)
  array.each { |i| p i } # O(n)

  array.each do |i|      # O(n) and nested O(n) -> O(n^2)
    array.each { |j| p i+j }
  end
end

Calculation O(n+n^2). We use n^2 for a nested array, but for a simple iterable array, we only use +n. In the formula, the dominant term is n^2, which stands for nested loops and has the most significant impact in terms of scale. In this case, we want to drop the rest of the formula and leave the dominant term as O(n^2) only.