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.
- 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.
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)
The amount of time is directly proportional by the number of entries, denoted by O(n)
Is when the time grows depending on 2 or more nested entries O(n2)
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.
An algorithm is a set of ordered, specific and limited instructions that solves a particular problem.
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
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.
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