Time Complexity

Time is Money!

Time complexity of an algorithm measures the time taken to execute each statement of code in an algorithm. It will provide information on how the execution time in an algorithm varies, either increasing or decreasing the number of operations in an algorithm.

NOTE: It is not going to examine the total execution time of an algorithm.

Big O Notation

is a metric for determining the efficiency of an algorithm by describing its time complexity.

Big O represents an algorithm’s worst-case complexity. It uses algebraic terms to describe the complexity of an algorithm.

It defines the runtime required to execute an algorithm by identifying how the performance of your algorithm will change as the input size grows.

But why do we need Big O?

It is an important topic for interviewers to ask about because it can have a big impact on the performance of a program. As a candidate, you should be able to explain time complexity in terms of Big O notation.

For example: You have been given a problem statement of Counting frequencies of array elements. Always solve the problem algorithmically first. You may start with a brute-force approach. A simple solution is to run two loops. For every item, count the number of times it occurs.

Time Complexity : O(n²)

But the interviewer says “This’ll work, but any ideas for how to do it more efficiently?”

Now you have to optimise the solution by analysing different Data Structures on the basis of time complexity. An efficient solution is to use HashMap. The best way to count the number of occurrences of each letter in a string would be to use a HashMap. This data structure would allow you to keep track of each number and how many times it appears in the array in an efficient manner.

Time Complexity: O(n)

(With enough practice, you’ll probably find yourself jumping straight to the optimised solution, skipping the more naive solution.)

Source

There are different types of time complexities used, let’s see one by one:

1. Constant time — O (1):

An algorithm is said to have constant time with order O (1) when it is independent of the input size n. For example:

public class Main
{
 public static void main(String[] args) {
  System.out.println("Hello World");      //Just a statement
 }
}

2. Linear time — O (n):

An algorithm is said to have a linear time complexity when the execution time rises linearly with the size of the input. For example:

public class Main
{
 public static void main(String[] args) {
  int n = 3;
  for(int i=0; i<n; i++){
      //The execution of statements will depend on n.
      System.out.println(i);
  }
 }
}

3. Logarithmic time — O (log n):

An algorithm is said to have a logarithmic time complexity when in each step it reduces the length of the input data. For example: Binary search

public class Main
{
    //You want to search for target element in a sorted array:
    static int binarySearch(int arr[], int target){
        int low = 0;
        int high = arr.length - 1;
        while(low<=high){
            //You will find the mid index & compare it with target element
            int mid = (low + high)/2;
            if(arr[mid]==target){
                return mid;
            }
            //If target is smaller than mid element, search the left part
            else if(arr[mid]>target){
                high = mid - 1;
            }
            //If target element is greater than mid, search the right part.
            else{
                low = mid + 1;
            }
        }
        return -1;              //If element is not present
    }
 public static void main(String[] args) {
  int a[] = {1,2,3,4,5,6,7,8};
  //Calling the method
  System.out.println(binarySearch(a,8));
 }
}

4. Quadratic time — O (n²):

An algorithm is said to have a non-linear time complexity where the execution time rises non-linearly (n²) with the size of the input. For example if we run nested for loops:

public class Main
{
 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.print(j + " ");
      }
      System.out.println();
  }
 }
}

Source

• O(1) — Excellent/Best
• O(log n) — Good
• O(n) — Fair
• O(n log n) — Bad
• O(n²), O(2^n) and O(n!) — Horrible/Worst

Time complexity for various data structures:

Source

Source

Would be lying if we said we haven’t been there!! Source

Upcoming topics for the blogs:

For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.