Clear concepts

Trying to explain something with ease and precision is way much harder on a second language, without examples or context, than on our native language, so I try to explain big O notation and an example of sorting algorithm in simple words.

Big O notation

The complexity given by the relation about the time that a function takes to run and the size of the given input.

Simple rules

• Arithmetic operations are constant.
• Value assignments are constant.
• Access elements by key or index are constant.
• Consider just the biggest case.
• Everything inside a loop must be multiplied n times defined by the loop limits.
• Get rid of coefficients.

Constant

When you have a simple statement or you know the exact number of times than a loop iterate it’s consider constant denoted by O(1)

Simple statement

Konown limit of loop

Linear

The amount of time is directly proportional by the number of entries, denoted by O(n)

Exponential

Is when the time grows depending on 2 or more nested entries O(n2)

Logarithmic

Time grows n half cuts of the given entry denoted by O(log n)

Time grows n time n half cuts of the given entry denoted by O(n log n) like quicksort algorithm.

Algorithms

An algorithm is a set of ordered, specific and limited instructions that solves a particular problem.

Sorting

Sorting algorithms are used to rearrange an array or list of elements according to a comparison operator. One of these algorithms is a quicksort algorithm with a complexity of O (n log n) that means it’s going to iterate on each one of the partitions of the original array.

This algorithm is conformed by 2 parts, partition and recursive calling

Partition:

The last element of the array is taken as a pivot, and we have two indexes j starting at the first element -1 and i as the first element. i it’s going to iterate until pivot -1.

If the array of i is lesser than the pivot j it’s going to increment by 1 and the elements of array on i and j are swapped, after the last iteration of partition we have the following array.

The next step is to swap the pivot and the element of array at j+1 ensuring that its the middle element of that part of the array.

Then we return j+1 and call partition into the left and the right side of the pivot.

Recursive calling

The partition method it’s gonna be called on each side of the partition until the index of the first element (l) is greater or equals the index of the last element of the partition of the array(m).

Here is the implementation of those two parts in java

recursive calling / parition method