Analyse Time and Space Complexity using Examples.

Let us look at a few examples to analyze the time and space complexity —

1. A simple access operation.

int accessElement(int[] arr, int index) {
        return arr[index];                   // Time complexity is O(1)
    }

In this example, we are just performing a single operation of returning an element at the index, hence the time complexity is O(1).

2. A for/while loop that runs for N input times.

boolean linearSearch(int[] arr, int target) {
        for (int element : arr) {           //Time complexity is O(N)                                           //it checks for N inputs in the loop
            if (element == target) {
                return true;
            }
        }

In this example, we are performing a linear search for N number of Inputs, hence the time Complexity is O(N).

3. Two for/while loops that run for N input times each.

void printPairs(int[] arr) {
        for (int i = 0; i < arr.length; i++) {   //Time complexity is O(N^2)
            for (int j = 0; j < arr.length; j++) {
                System.out.println("(" + arr[i] + ", " + arr[j] + ")");
            }
        }
}

In this example, we are operating on the array by iterating through the loop twice, by comparing each element with all other elements, hence the time complexity is O(N*N) — O(n²).

4. For /while loop that runs for only N/2 input times.

void check(int[] arr) {
        for (int i = 0; i < arr.length; i+2) {   //Time complexity is O(N/2)
            System.out.println(arr[i]);
        }
}

In this example, we are operating on the array by iterating through the loop by incrementing each iteration by 2, hence the time complexity is O(N/2).

5. A function that searches half the input size in each iteration.

int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
                                        //Time Complexity is O(logN)
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return -1;
    }

The time complexity is O(logn) because, in each iteration, the size of the search space is halved.

6. Sorting any given input array or structure.

void mergeSort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }

        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        mergeSort(left);
        mergeSort(right);

        merge(arr, left, right);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        while (i < left.length) {
            arr[k++] = left[i++];
        }

        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

In this example, mergeSort implements the merge sort algorithm. The time complexity of merge sort is O(nlogn) because the array is repeatedly divided into halves O(logn) and then merged O(n).

7. Cubic operation loops

void cubicOperation(int[] arr) {
        int n = arr.length;
                                          //Time Complexity is O(n^3)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    // Perform some operation on elements
                    System.out.println(arr[i] + " " + arr[j] + " " + arr[k]);
                }
            }
        }
    }

In this example, the cubicOperation method has three nested loops, each iterating over the array.

The operation inside the innermost loop is performed for every combination of three elements from the array.

As a result, the time complexity of this algorithm is O(n3). As the size of the array increases, the running time grows cubically.

In the next blog, I shall cover the most common sorting algorithms and their time and space analysis.