Big O notations.

You might have heard this fancy words like this algorithm takes O(n) time to run.

In order to write good code, it should be salable. Well how do I know is my code scalable ? The answer is simple it depends on big O.

I know that but tell me how to calculate it.
Best way to understand it is using examples.

Constant time complexity - O(1)

let's take an example where we have to access first element of an array.
This is a program which returns first element of given array.

  public static void getFirstElement(int n) {
          public static void printFirstItem(int[] items) {
    System.out.println(items[0]);
}

How quicky runtime grows as input becomes arbitrarily large is Big O.

Big O of this algorithm is O(1) or constant time complexity.
If we have 10 elements or 100000 elements, for accessing 1st element its same amount of effort.

Linear time complexity - O(n)

Again let's take an example.
This is a program which prints all elements of an array.

public static void printAllItems(int[] items) {
    for (int item : items) {
        System.out.println(item);
    }
}

Again how quicky runtime grows as input becomes arbitrarily large is Big O.

Big O for this algorithm is O(n). n is number of elements in array . This loop will print 10 items if we have 10 items in array, likewise 1000 for that size of array. So, basically for n elements in array it will print item for n times.

Hence O(n) time complexity.

Quadratic time complexity - O(n^2)

Example OP guys.
This program is like multiplication of an array with itself.
So we are taking each element of array and multiplying it with every element of that array.

public static void printAllPossibleOrderedPairs(int[] items) {
    for (int firstItem : items) {
        for (int secondItem : items) {
            System.out.println(firstItem + ", " + secondItem);
        }
    }
}

It's a for each loop in java. So what's the catch?
First for loop will make loop run for n times (n is size of array). Now second for loop will run for n times for each element of 1st loop.

Basically it's like
for 1st element -> 1 x n times
so for n elements -> n x n times
Hence it's O(n^2)

Keep in mind.
All operations which are done by CPU, specifically are ALU.
Takes O(1) time. As they are done by CPU within fraction of seconds.

Stay tuned for next blog where we discuss on how to calculate Big O for any algorithm