DEV Community: Nemanja Milosavljevic

Big O

Nemanja Milosavljevic — Mon, 11 Oct 2021 15:25:47 +0000

Do you know what the Big O stands for?

Yes! Erm... I have a friend his name is Orestis he is big enough, therefore, we call him Big O, is it not?!
Well, not really.
Erm... Big Omar? Or, no, no, Big Otto, right?
Well, you are almost there. Big O can be our friend, it usually is, but its name is neither Orestis nor Otto or Omar.

Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others collectively called Bachmann–Landau notation or asymptotic notation.

That is what Wikipedia is saying, not me, all possible complaints to them then.

Simplified, Big O describes the complexity through mathematical terms, precisely algebraic. We can see it in an example like this. O(n²), which is called Big O squared. The letter n is nothing but an input size of given elements, let's say an array of n integers, and the function f(n) = n² shows us how big the input is. Quadratic time complexity has a growth rate of n². If the input is size 2, it will do four operations, if the size is 4 it will do 16 operations and so on.

Shall we write an example for an Algorithm that runs in n2 time complexity right now and then discuss it in the detail? Just bear with me here. I promise it is going to be fun.

A typical example would be Selection Sort. For the definition and more detailed functionality of the Selection sort, you can read here.

Now then

..back to the implementation.

void sort(int array[]) {
        int n = array.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (array[j] < array[minIndex ]) {
                    minIndex  = j;
                }
            }
            int temp = array[minIndex ];
            array[minIndex ] = array[i];
            array[i] = temp;
        }
   }

Alright, let's look at this sorting algorithm in detail. Shall we determine what Big O it has and why?

        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (array[j] < array[minIndex ]) {
                    minIndex  = j;
                }
            }
            int temp = array[minIndex ];
            array[minIndex ] = array[i];
            array[i] = temp;
        }

If we look at the outer for loop of our algorithm, that would mean that our algorithm will run at O(n) time, at least at the first glance. Why? For the n input integers, for loop will repeat n-times. That has been defined in the loop condition, it is straightforward, and that's all about the outer for loop.

            for (int j = i+1; j < n; j++) {
                if (array[j] < array[minIndex ]) {
                    minIndex  = j;
                }
            }

Alright, let's tackle the last portion of the code now. We would find that the inner loop will repeat for 1+2 … + n times, which equals n(n-1)/2 times. If we multiply this out, we will end up getting n²/2-n/2.
When we calculate big O notation, we only care about the dominant terms, and we do not care about the coefficients, therefore we can avoid all the values except for n² which will point to our definite time complexity range. We write it as O(n²) as our big O value.

Definition of dominant term

The mathematical term greater in absolute value than any other (as in a set) or than the sum of the others.

For instance, n² grows faster than n, so if we have the following quadratic equation an² + bn + c. Where a,b,c are known numbers, and a ≠ 0. We only care about the dominant term for numerators and denominators in the end. Finally, it'll lead us to the final big O(n²) value.

At this point, we ask ourselves if there is a little O or something similar?
Well, Yes, there is indeed, and we will most certainly mention it.

Big O, Little O, and the rest of the gang..

Big O (O()) stands for the upper bound of the complexity.
Little o (o()) stands for the upper bound excluding the exact bound.
Omega (Ω()) stands for the lower bound of the complexity.
Theta (Θ()) stands for the exact bound of the complexity.

It is about time to look at the complexity order across the BigO, from the least complex to the most complex ones.

Big O Complexity

O(1) has the least complexity (constant complexity)
O(log(n))
O(n)
O(nlog(n))
O(n²)...O(n⁴), O(n⁵)...O(n⁹⁹)..and so on
At some point here, we will face some inefficient algorithms with the big O of O(N!) factorial, which one can rarely face in day to day algorithm solving problems, especially coding ones due to its high inefficiency.

Time & Space Complexity

So far, we have only been discussing the time complexity of the algorithms or how fast is an algorithm. However, what also matters is the space the program takes to complete the task. The space complexity is related to how much memory the program will use, and therefore is also an important factor to take into count.

The space complexity works similarly to time complexity. For example, the selection sort that we have worked with so far has a space complexity of O(1). Because it only stores one minimum value and its index for comparison, the maximum space used does not increase with the input size. It means that it doesn't need any additional memory space to store values while running. Of course, some algorithms can and will use additional space, and its big O can be O(n).

An example of such an algorithm would be the Bucket Sort. Bucket sort sorts the array by creating a sorted list of all the possible elements in an array, then increments the count whenever the element is encountered. In the end, the sorted array will be the sorted list elements repeated by their counts.

Bucket Sort Visually:

*Image taken from Wikipedia.

Bucket sort works as follows:

Set up an array of initially empty buckets.
Go over the original array, putting each object in its bucket.
Sort each non-empty bucket.
Visit the buckets in order and put all elements back into the original array.

Last but not least

Complexity Expectance

The complexity can be analyzed as best case, worst case, average case and expected case.
Let’s take insertion sort, for example. Insertion sort iterates through all the elements in the list. If the element is larger than its previous element, it inserts the element backwards until it is larger than the previous element.

*Image taken from Wikipedia.

If an array has been initially sorted, then no swapping will be made. The algorithm will iterate through the array once, which has the time complexity of O(n). Therefore, we would say that the best-case time complexity of insertion sort is O(n).

To Wrap up:

Big O notation is a mathematical analysis applied by the algorithm. The results may defer, so we always have to take the edge cases into count. At this particular moment, we should be able to understand how and when to use Big O analysis and manipulate our best performance.
The whole story is based on my own experiences and researches. Please let me know if I have missed something or wrote something that brought you to confusion. There are plenty of articles on this topic, and they are waiting for you to read them Orestis, Omar, and you Otto.

Road to algorithm world

Nemanja Milosavljevic — Tue, 05 Oct 2021 15:36:31 +0000

What is an algorithm? I like to think that an algorithm is a set of rules specifying how to solve a problem. An algorithm can be defined outside of computer science, in Mathematics, nature or traffic. In computer science, an algorithm is abstract and does not have a machine implementation.

The most important 'tool' to manipulate while coding is data structures, and precisely that is the starting point of the road to algorithms. Data structures are simply a way to organize data. However, to be more specific, who'd say better than Wikipedia, right?

A data structure is a collection of data values, the relationships amongst them, and the functions or operations that can be applied to the data.

It is the right time to tackle the topic of complexity analysis. This is a process of determining how efficient an algorithm is. Therefore, we shall focus on two dimensions, time and space complexity.

Time complexity is a measure of how fast an algorithm runs, and it is expressed using Big O notation.

Space complexity is a measure of how much auxiliary memory an algorithm takes, and it is also expressed by using Big O notation.

Memory is a big topic, therefore we could define here some base-lines. Let's say that memory is the place, or more precisely a layer where all data is stored. How? Well, there are the following points:

Data stored in memory is stored in bits and bytes.
Bytes are able to point to other bytes in memory. (Referencing other data).
Byte sizes, like 4 bytes, or 8 bytes in the case of 32-bit or 64-bit integers.

Big O notation is the most important tool to generalize the time or space complexity of an algorithm. These values aren't fixed, so they may vary depending on the input. Therefore, we measure from the most performant to the least performant as, O(1) as constant complexity, or O(log(n)), O(n), O(n^2), O(n^3)..etc..etc.

Data structures are generally presented in four forms:

Linear: arrays, lists.
Tree: binary, heaps, space partitioning etc.
Hash: distributed hash table, hash tree etc.
Graphs: decision, directed, acyclic etc.

Having these tools mentioned and collected in our 'backpack', we have pretty much everything to tackle, define, and then write our algorithms in the most efficient way to a given occasion.

Hands on..

How we are going to use all these items that we have in our 'techy backpack'? Well, we need a problem to start. Fair enough, here is one, an easy one to begin.

Here is the problem from LeetCode . Exactly what we need.

`Two Sum`

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

For an instance:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Now, when we have understood our problem, we shall cheer. 'Yeeees!!!'
We know how to tackle the problem, we open our 'backpack' and choose our tools.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length -1; i++) {
           int firstNumber = nums[i];
           for (int j = i + 1; j < nums.length; j++) {
              int secondNumber = nums[j];
              if (firstNumber + secondNumber == target) {
                 return new int[] {firstNumber, secondNumber};
              }
           }
        }
        return new int[0];
    }
}

'WooooooW', it works!

Hmmm... Yes, it works indeed, but as we are beginners on this road, we have used brute force technics, which means that we were passing through our array with two integers, respectively i and j, and then we have tried to sum up every combination between the two. Therefore we have used, two nested for loops to iterate throughout the array. Shall we look at the already mentioned Big O and its time and space complexity?
Alright, the space complexity we've got is O(1). Splendid, couldn't be better, a constant space, which means no additional memory was used to store the data. Now then, we end up with an O(n^2) time complexity. The reason for this was iterating through two nested loops in regards, to sum up, every combination. Well, we have to say that our algorithm seems to be very slow. What if we would have an n-sized array instead of just four integers in our example. Well, that would be very slow. So, can we do it better, now?

Let's give it another try.

class Solution {
  public static int[] twoSum(int[] nums, int target) {
    Set<Integer> numbers = new HashSet<>();
      for(int number : nums) {
        int match = target - number;
        if (numbers.contains(match)) {
          return new int[] { match, number };
        }
        numbers.add(number);
    }
    return new int[0];
  }
}

It works again! We are doing fantastic, I must say. Let's talk again to our Big O friend. Now we have a slightly better situation. We have improved our time complexity from O(n^2) quadratic time to the O(n) time. We got rid of the inner for loop, and we iterate only once throughout an array. We have introduced the HashSet data structure, and it helps us to store the potential matching combinations, and after every iteration, we look up the hash table to see if we summed up to the target number. Way faster than the previous solution. We have improved the time complexity significantly, and our algorithm is way faster now. However, by using the HashSet, we allocated some memory. Remember, we had to store our matching combinations somewhere, and that means our space complexity disimproved. It is O(n) right now, instead of O(1) in the previous example.

So what's the better approach now?

Well, in the first example we had O(n^2) time | O(1) space complexity, and
now we have O(n) time | O(n) space complexity. I think we have improved our algorithm in general. Now, let's see if we can do even better.

class Solution {
  public static int[] twoSum(int[] nums, int target) {
    Arrays.sort(nums);
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
           return new int[] { nums[left], nums[right] };
        } else if (sum < target) {
           left++;
        } else if (sum > target) {
           right--;
        }
    }
    return new int[0];
  }
}

The third time success! Marvellous manoeuvre! Let's go and talk to our Big O friend there.

Ok, Big O, what do you have for us this time?
Well, I have good news for you.

We might know that a good sorting algorithm like quicksort, mergesort or heapsort can run in O(n*log(n)) time. So that explains sorting an array straight on the top, and then we can find the sum in O(n) time, and we do not use any additional space, so again we have improved the space complexity back to O(1). With this set up we are allowed to do the next thing. As the array has been immediately sorted, we can surely put the left pointer at the beginning of an array, and the right one at the very end of an array. We will sum up the elements in the first cycle, and compare if the sum is equal to the target number. In the case of truth, we simply return the positions of the pointers, accordingly, if the sum is less than the target number we will have to increase the left pointer for one position to increase the sum of pointers. If the sum is, however, bigger than the target number, that would mean that we have to move the right pointer to the one position to the left, in regards to decrease the sum of pointers.

To sum up, we have sorted an array immediately, and then we have iterated one time throughout the array. Finally, we were able to find our third solution in O(n*log(n)) time | O(1) space complexity. This is a very cool solution but was it better than the previous one? Well, it depends on what are our needs. Do we want to care more about time or space complexity performance? I'll just let you decide for yourself.

Final thoughts

This was a showcase of how we can apply various technics, memory, and data structures to write performant algorithms. We've started with brute force technics which is usually the least performant one, and then we have tried to see what could be the possible improvement, searching for the better tools inside of our 'backpack'.

I like to use this step-by-step solution. "Try to improve!" An old adage in carpentry is to Measure Thrice, Check Twice and Cut Once!