Different time complexities a programmer must know

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:

• O(1) – Constant Time Complexity: An algorithm has a constant time complexity if it takes the same amount of time to execute regardless of the input size. For example, accessing an element in an array using its index has a constant time complexity of O(1).

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]);
}

• O(log n) – Logarithmic Time Complexity: An algorithm has logarithmic time complexity if its time to execute increases logarithmically with the input size. For example, binary search algorithm has a logarithmic time complexity of O(log n).

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;
}

• O(n) – Linear Time Complexity: An algorithm has a linear time complexity if its time to execute increases linearly with the input size. For example, traversing an array has a linear time complexity of O(n).

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

• O(n log n) – Linearithmic Time Complexity: An algorithm has a linearithmic time complexity if its time to execute increases as n multiplied by logarithm of n with input size. For example, the merge sort algorithm has a linearithmic time complexity of O(n log n).

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];
    }
}

• O(n^2) – Quadratic Time Complexity: An algorithm has a quadratic time complexity if its time to execute increases with the square of the input size. For example, a nested loop that compares each element in an array with every other element in the same array has a quadratic time complexity of O(n^2).

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]);
        }
    }
}

• O(2^n) – Exponential Time Complexity: An algorithm has an exponential time complexity if its time to execute doubles with every addition to the input size. For example, the brute-force approach to solve the traveling salesman problem has an exponential time complexity of O(2^n).

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:

• For sequential operations, the time complexities are added together. For example, if we have a program with two sequential operations, one with time complexity O(f(n)) and the other with time complexity O(g(n)), then the composite time complexity of the program is O(f(n) + g(n)).
• For nested operations, the time complexities are multiplied. For example, if we have a program with an outer loop with time complexity O(f(n)) and an inner loop with time complexity O(g(n)), then the composite time complexity of the program is O(f(n) * g(n)).
• For branches, we take the maximum time complexity. For example, if we have an if-else statement where the if branch has time complexity O(f(n)) and the else branch has time complexity O(g(n)), then the composite time complexity of the statement is O(max(f(n), g(n))).

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:

• quadraticTime: O(n^2)
• logarithmicTime: O(log n)
• linearithmicTime: O(n log n)

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).