Big O Notation

Big O notation describes the worst case scenario for an algorithm.

O(1):
Doesn't matter the size of the dataset, it will always execute in the same time.

def change_first_element(array, element)
 array[0] = element
end

O(N):
It takes a linear time range.

def looper(array)
  array.each {|e| puts e }
end

O(N2): It means that the function will perform proportionally to the square of the input data size. Bubblesort is an example of O(N2) algorithm, it uses two chained loops that irate over the data.

class Array
  def bubblesort!
    length.times do |j| # iterates over the dataset
      for i in 1...(length - j) # nested iteration
        if self[i] < self[i - 1]
          self[i], self[i - 1] = self[i - 1], self[i]
        end
      end
    end
    self
  end
end