What is the Big O notation? A little bit of theory.

Read Time:4 Minute, 49 Second

I will give you a small portion of a theory today. Todays article will get you familiar with the concept of Big O notation. Let’s see the very basics.

This a very important concept in computer science. It shows how much runtime changes with the number of elements. Big O notation describes how the runtime scales and showing the time complexity of the algorithm (method/function).

It’s a term that is commonly used during job interviews so if you want to crack it you should be familiar with it 🙂

Writing a function or even a whole functionality that consist of building blocks like algorithms implemented by methods we strive to have them as optimal as we can. I mean that would be in an ideal world but I as a programmer usually do that. We can calculate the time complexity just by analyzing our code, the flow and number of elements that flows through it. Not literally of course.

Big O notation is written: like O(n) – where n is the size of the problem. What it means exactly? Check this out. Let’s say we have a loop:

        int[] arr = new int[690];

        for (int i = 0; i < arr.length; i++) {
            arr[i] += i+2;
            System.out.println("element: " + i);
        }

What’s the Big O for that piece of code? The runtime increases with the number of elements. The loop iterates through the array once. So the relationship is linear. The Big O is: O(n) – n elements of the array. In this case we could write it as O(i) – as we have a variable i in our code.

        int[] arr = new int[690];
        int[] arr_two = new int[100];

        for (int i = 0; i < arr.length; i++) {
            arr[i] += i+2;
            System.out.println("element: " + i);
        }

        for (int j = 0; j < arr_two.length; j++) {
            System.out.println("element: " + j);
        }

I have added another for loop to my chunk of code. What is the Big O? We have two for loops that iterates over two different arrays with different sizes. The Big O is: O(i+j) – we need to add the sizes of our element sets.

    for (int i = 0; i < arr.length; i++) {
            System.out.println("element: " + i);
            for (int j = 0; j < arr_two.length; j++) {
                System.out.println("element: " + j);
                if (i == j) {
                    System.out.println("Nuber from first array " + arr[i] + " and from the second one " + arr_two[j] + " are equal!");
                }
            }
        }

What about that? We have nested for loops. Each one iterates through different arrays with different sizes. The Big O is: O(i*j) – we multiply the sizes of the given set of elements. Very common mistake is to write it as O(n^2). Remember that the variable in O function is just a variable. It can be any letter we need. In this case the numer of elements for each array is represented by i and y therefore I have used those letters.

Best, average, worst case scenarios

The complexity calculated by Big O may differ depending on the input we put into the algorithm. We differentiate between the best and worst scenarios. In this article I’m talking about worst/average case scenarios. When printing out all elements from two arrays it’s always O(n^2) no matter what. But when searching or sorting we can have some certain sets of elements that reach the best or the worst boundary.

For instance, when searching using linear search the first element on the list is the one we’re looking for it will be faster than binary search that has usually satysfying complexity of O(log n).

That’s the basics. Let’s check some real life examples. We’ll try to estimate the Big O for some well known searching and sorting algorithms!

Bubble sort:

void bubbleSort(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 0; i < n-1; i++) 
            for (int j = 0; j < n-i-1; j++) 
                if (arr[j] > arr[j+1]) 
                { 
                    // swap arr[j+1] and arr[i] 
                    int temp = arr[j]; 
                    arr[j] = arr[j+1]; 
                    arr[j+1] = temp; 
                } 
    }

We have two nested for loops. They sort elements within the array which has n elements (or i elements) – therefore we have O(n^2) here.

Binary search:

Binary search algorithm works on a sorted array. I provides O(log n) at average – that’s a really good performance here. It works in a way that by each iteration it cuts in half the array so it has less and less elements to iterate through. Firstly it has n/2 elements, then n/4, n/8, n/16 and so on. The time complexity decreases logarithmicly.

 private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                     long key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            long midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

This code is pasted from Jdk 11 Arrays class implementation. In the first parameter we give the array, in second the starting index (if we need to search throug entire array we pass 0), the endinx index (we should pass array length if we need to search through entire array), and the element we are looking whole. I advise you analyze this code as the algorithm is really cool and may commonly used (you may encounter it on your job interview!).

That’s it when it comes to basics of Big O notation. You’ve got familiar with the basic concepts and some real life examples.

Should you have any questions, don’t hesitate to reach me via linkedin, facebook, email or via comments.