Site icon Concurrent Core

Different time complexities a programmer must know

ajagekar.s.d
Time Complexity
Time Complexity

POST #5 Calculating the time and space complexity of a Java program is an important step in analyzing its efficiency and performance. Here are some general steps for calculating the time and space complexity of a Java program:

  1. Identify the algorithm: The first step is to identify the algorithm used in the Java program. Algorithms are step-by-step procedures for solving a problem, and their time and space complexities depend on their specific implementation.
  2. Count the operations: Once the algorithm is identified, count the number of basic operations that are performed by the program. Basic operations include arithmetic operations, comparisons, and assignments.
  3. Determine the worst-case scenario: In order to determine the time complexity of a Java program, you need to determine the worst-case scenario for the algorithm. This is the scenario where the algorithm takes the most time to execute.
  4. Use Big O notation: Use the Big O notation to express the time complexity of the Java program. Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.
  5. Analyze space complexity: To analyze the space complexity of a Java program, determine the amount of memory used by the program as a function of the input size.
  6. Use Space Complexity Notation: Similar to Time complexity notation, use space complexity notation (like O(1), O(n), O(n^2), etc.) to express the space complexity of the Java program.

Overall, calculating the time and space complexity of a Java program involves understanding the algorithm used, counting the basic operations, determining the worst-case scenario, and expressing the complexity using Big O notation (for time complexity) and space complexity.

Below are some examples of different time complexities that can be encountered in algorithms:

public static void constantTime(int[] arr) {
    // Accessing the first element in the array takes the same amount of time
    // regardless of the input size
    System.out.println(arr[0]);
}

public static int binarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    
    while (low <= high) {
        int mid = (low + high) / 2;
        
        if (arr[mid] < key) {
            low = mid + 1;
        } else if (arr[mid] > key) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    
    return -1;
}

public static void linearTime(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
}

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

public static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[arr.length];
    int i = left;
    int j = mid + 1;
    int k = left;
    
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    
    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }
}

public static void quadraticTime(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + " " + arr[j]);
        }
    }
}

public static int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    
    return fibonacci(n - 1) + fibonacci(n - 2);
}

These are just a few examples of the many possible time complexities that can be encountered in algorithms.

Note that some of these examples are intentionally simplistic for the purpose of illustrating the time complexity, and may not be the most efficient or practical implementations of the algorithms.

To calculate the composite time complexity of a program that consists of multiple functions or operations, we can use the following rules:

Let’s consider an example program with three functions:

public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 5};
    quadraticTime(arr);
    logarithmicTime(arr.length);
    linearithmicTime(arr);
}

public static void quadraticTime(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + " " + arr[j]);
        }
    }
}

public static void logarithmicTime(int n) {
    int i = n;
    while (i > 1) {
        i /= 2;
    }
    System.out.println(i);
}

public static void linearithmicTime(int[] arr) {
    Arrays.sort(arr);
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
    }
    System.out.println(sum);
}

The time complexity of each function is as follows:

The composite time complexity of the entire program can be calculated by adding the time complexities of the three functions, since they are executed sequentially:

O(n^2) + O(log n) + O(n log n) = O(n^2 + n log n)

Therefore, the composite time complexity of the program is O(n^2 + n log n).

Exit mobile version