Time Complexity of Algorithms (Big O also covered)

Time complexity of an algorithm is the time take by an algorithm to complete the process. Now we need a way to define/express (metric) the time complexity for an algorithm. For example, to define/express (metric) weight of something, we use Kg/Lbs. In the world of algorithms, we use Big O to define/express time complexity.

When we define time complexity for any algorithm, we take into account worst-case time complexity and not best-case time complexity. 

Worst-case time complexity :- Maximum time taken by an algorithm for any input size.

Best-case time complexity :- Minimum time taken by an algorithm for any input size.

How to calculate time complexity ?

Now we have take into account that we will be using Big O notation as the metric for calculating time complexity.

Big O -- What is that ?

Big O for any algorithm determines how an algorithm responds (take time) to different variety of inputs or may be how much slow an algorithm is if the input is very large.

Note:-
An algorithm is =>

(a) Linear -- If doing something with every item in one dimension.
(b) Quadratic -- If doing something with every item in two dimension.
(c) Logarithmic -- Dividing the item in half in every iteration.



Note:- We ignore constants in Big O

Lets jump on to coding examples to figure out Big O

Example 1 :-

public void printText (int N){
     
System.out.println("We are calculation big o");   //This line is also example 2 (O(1))

for(int i=0;i<N;i++){
     System.out.println(i);
}

}

In the above program, System.out.println("We are calculation big o");    is a statement which is constant and will not change based on input size. So we can ignore this statement and statement/variables like this when determining Big O and treat them as constants.

Time complexity for the for loop will be linear, which means time taken by for loop will be directly proportional to the size of input which is N in this case.

When we say linear, that means O(N) or Order of N. Linear is more in terms of graphical representation of O(N).

This is linear because line is straight.

Example 2 :-

Consider the below example:-

public int printText (int N){
     
     return N;
}

Time complexity or Big O for this program will be O(1). The reason is because irrespective of how large the input is, the time will always be same.

O(1) is constant time which is also considered as the best-case scenario

Example 3 :-

Consider the below example:-

public void performOperation(int N){

     

     for(int i=0 ; i<N ; i++){

              for(int j=0 ; j<N ; j++){

                  System.out.println("printing the value");

             }

      }

}

In the above case, there are two for loops iterating twice for give input. So time complexity in this case is quadratic. O(n^2) is the big O in this case.

Below is the comparison graph for the above three examples:-

Example 4 :-

Consider the below example:-

public void performDivideAndConquere( int target){

     while(low <= high) 
{
  mid = (low + high) / 2;
  if (target < list[mid])
    high = mid - 1;
  else if (target > list[mid])
    low = mid + 1;
  else break;
}

   }

The above algorithm break any given input into halves to search a particular field like we do in any divide and conquere type of algorithm. The time complexity of this algorithm will be logarithmic because this is opposite of growing exponentially 2 times and actually dividing the input into half with each iteration.

Big O for this algorithm will be Log₂ (N) or just Log (N)

Example 5 :-

Example 4 has a time complexity of Log (N). What if the program in example 4 is in itself is also repeated N times . In that case the time complexity of such an algorithm will be  N * Log (N)

The running time consists of N loops (iterative or recursive) that are logarithmic, thus the algorithm is a combination of linear and logarithmic.