Tag: Big O

Selection sort in Python

Introduction Selection sort is a simple in-place (i.e. no auxiliary memory) comparison based sorting algorithm. It is an inefficient algorithm with O(n2) running time as it uses two nested loops. Here is a summary of steps how the algorithm works: Given an unsorted list Start with the first element on the left side Scan all

Insertion sort in Python

Introduction Insertion sort is a simple in place (i.e no need for an auxiliary memory) sorting algorithm. It is an efficient algorithm for small data sets, specially for lists that are partially sorted. For more information about how sorting works, you may refer to the following article For more in depth information about insertion sort

Dynamic Programming Longest Increasing Sub Sequence

Longest Increasing Sub Sequence Welcome to the 6th part of our discussion on Dynamic Programming. You can refer to the first article (introduction) here. In this article we are going to discuss the "Longest Increasing Sub Sequence" problem which can be solved efficiently using Dynamic Programming. Problem Definition Given a sequence of numbers [A1 ..

Dynamic Programming Longest Common Subsequence

Longest Common Subsequence Welcome to the 4th article on Dynamic Programming. You can refer to the first article (introduction) here. I will be using the shortcut LCS to refer to longest common sub-sequence. Let us get started. Introduction One of the applications of "Longest Common Subsequence" problem is comparing DNA strings to see how similar