Basic Big O notation and Selection Sort

Phil B — Wed, 17 Feb 2021 20:12:24 +0000

Big O Notation Summary

To be brief, Big O notation is used to describe the complexity or performance of an algorithm. Big O specifies the worst-case and is used to describe the time and space complexity of an algorithm. Selection Sort has a worst-case performance of O(n^2).

Time Complexity

O(1)

O(1) is constant, meaning the time complexity does not change even with the data size differing.

def find_the_first_word(word_array)
  word_array[0] # // Directly returning first word of array
end
find_the_first_word(['first word', 'second word', 'third word'])
=> "first word"

will return "first word", as the method knows exactly where to look.

O(n)

O(n) is linear, meaning the time complexity correlates to the size of the data structure. For this example I will use some interpolation to give you a better visual idea of whats happening here. If an array has a size of 3, O(n) means that it will iterate through that array 3 times unless a conditional states otherwise, although the worst-case is still going to be O(n)

def print_all_words(word_array)
  count = 0
  word_array.each_with_index do |word, index| 
    puts "Iteration number: #{index + 1} - Word: #{word}"
    count += 1 # // Add to count each iteration
  end
  puts word_array.length === count # // Just to show that iterations happen `n` times.
end
print_all_words(['first word', 'second word', 'third word'])
Iteration number: 1 - Word: first word
Iteration number: 2 - Word: second word
Iteration number: 3 - Word: third word
true

Selection Sort Summary

Selection Sort is an algorithm that takes in an unsorted array of numbers and at each iteration places the smallest number at the beginning of an unsorted list. Selection Sort is a great place to start while learning algorithms which is why I've decided to talk about.

This algorithm is inefficient with handling large lists of numbers, though performs well on small lists. It is an in-place sorting algorithm, meaning no additional temporary storage is necessary beyond the size of the original list.

O(n^2)

O(n^2) is quadratic, meaning that the time complexity correlates to the squared size of the data structure. This usually means that nested loops will be involved, hence O(n^2), the size of the input (n), squared. Every iteration of this algorithm selects the smallest integer and moves it to the start of the array. As you could imagine, with Selection Sort, using a small set of data this would be an suitable choice to sort numbers, but as the data grows it could be a good time to seek a more efficient algorithm to sort your data.

def selection_sort(array)
  n = array.length - 1 # // Sets integer value for the times loop
  n.times do |i|
    min = i # // Sets minimum value
    for j in (i + 1)..n # Becomes quadratic with nested loop
      min = j if array[j] < array[min]
    end
    array[i], array[min] = array[min], array[i] if min != i # // Swaps array[i] and array[min] if min is not equal to i, meaning the array is now sorted.
  end
  array # // Returns array of sorted integers
end
selection_sort([4,5,6,22,1,3])
=> [1, 3, 4, 5, 6, 22]

More on Big O Notation here.
More on Selection Sort here.