# Big O

Why Big O

Big O is used to compare algorithms and analyze the efficiency of an algorithm, since comparing the time taken to execute an algorithm is not very accurate, because different computers have different processing speed's and an algorithm might run faster or slower depending on computer specifications.

What is big O?

To put it simply it is a way of analyzing an algorithm or a function with respect to the size of the input. Here input could be an array or a string anything.

To better understand let us say you have to send a file to your friend, you can do it by sending it online or you could go to him and hand it over, here if you choose to send it online it takes linear time i.e O(n) see the image below, if your file is 10MB it takes say 4 seconds if your file is 20MB it takes 8 seconds and if your file is 1TB then it might take even a day, so the time complexity to send the file depends on the input size, the time increases linearly as input increases. But if you choose to go over and hand it to him that is constant time O(1) (see the image below), i.e the time to send doesn't depend on the size of the file it takes the same amount of time to deliver 10MB or 1TB.

So Big O is a measure of the increase of time with respect to the input size.

Now let us look at some algorithms and find their time complexities

Ex 1: The following program prints all the elements in an array one by one

 public static void traverseArray(int[] array) {
        for (int i : array) {
            System.out.println("i :" + i);
        }
    }

Here the time complexity is O(N)linear time where N is the size of the array, i.e the time taken to execute increases linearly with an increase in input size i.e array size, because we have to do an operation i.e printing the element for all elements in the array, assume one operation takes one second and if we have 5 elements the total time is 5 seconds and if we have 20 elements the total time is 20 seconds i.e the time grows linearly with respect to the input.

Ex 2: The following program prints all pairs of elements in an array

public static void traverseArray(int[] array) {
        for (int i : array) {
            for (int j : array) {
                System.out.println("(" + i + "," + j + ")");
            }
        }

Here the time complexity is O(N*2) where N is size of the input.
why O(N2)? because for each element there is O(N) work to be done in the inner loop, and this has to be repeated for every element in the outer loop so big O becomes O(N*N) i.e O(N*2).

TO get a better understanding checkout these resources:
Youtube video
examples of big O analysis