Time Complexity

Example 2:

public static void main(String[] args) {

       int n=3;

       for(int i=0;i<n;i++)
            System.out.println("Coding Ninjas");

}

You can also try this code with Online Java Compiler

Run Code

Output

Coding Ninjas
Coding Ninjas
Coding Ninjas

You can also try this code with Online Java Compiler

Run Code

In the above example, we have taken input n=3, applying the loop till input size n. ‘Coding Ninjas’ will be printed according to the input size given.

Therefore, this has a time complexity of O(n).

Example 3:

public static void main(String[] args) {

         int n=3;

        for(int i=0; i < n; i++) {
        
             for(int j=0; j < n;j++) { 
             
                  System.out.println("Coding Ninjas");
            }
       }
}

You can also try this code with Online Java Compiler

Run Code

Output

Coding Ninjas
Coding Ninjas
Coding Ninjas
Coding Ninjas
Coding Ninjas
Coding Ninjas
Coding Ninjas
Coding Ninjas
Coding Ninjas

You can also try this code with Online Java Compiler

Run Code

In the above example, we have taken input n=3, applying the nested loops to input size n. ‘Coding Ninjas’ will be printed n*n times.

Therefore, this has a time complexity of O(n^2).

Example 4:

public static void main(String[] args) {

       int n=6;
       int arr[]=new int[] {1,2,3,4,5,6};
       int low=0,high=n-1;
       int target=3;

       while(low <= high) {

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

You can also try this code with Online Java Compiler

Run Code

This is the code for binary search, which follows the divide and conquer approach. The algorithm’s running time is proportional to the number of times N can be divided by 2. 

Therefore, the time complexity of this algorithm will have a Logarithmic, i.e., O(log n).

Example 5:

void quicksort(int list[], int left, int right)
{
    int pivot = partition(list, left, right);
    quicksort(list, left, pivot - 1);
    quicksort(list, pivot + 1, right);
}

You can also try this code with Online Java Compiler

Run Code

The above example is the logic of the QuickSort algorithm which also follows the divide and conquer approach, just like Binary search, but here, we repeat the iteration N times.

Hence time complexity will be n*log( n ).

Read More - Time Complexity of Sorting Algorithms and  Euclid GCD Algorithm

FAQ’S

1). What is the difference between Space and Time Complexity?
Time complexity is the amount of time the code is required to be executed. Whereas space complexity is the amount of space needed by the code.

2). Rank the following by growth rate: n, 2 log n, log n, log (log n), log2 n, (log n) log n, 4, (3/2)^n, n! ?

Rank in increasing order of growth rate is 4,  log (log n), log n, log2 n, (log n)log n, 2 log n, n, n!, (3/2)^n.       

Key Takeaways

This blog has discussed how time complexity deals with the time required to execute a program.

We learned to compute time complexity and how important it is to keep in mind to write good code. 

Check out this article - Balanced Parentheses

Also, don’t forget to practice the wide variety of DSA problems frequently asked in interview rounds readily available on Coding Ninjas Studio. 

Happy coding!