Task is to create a code in O(n log n), what is the time complexity of this code that I wrote?

Question

I'm learning big O and time complexity and I find it hard to understand. Can you help me understand the time complexity for this code that I wrote?

Basically the task is to go through an array of numbers and count the number of pairs that satisfies arr[i] > arr[j]. Like for the array given in this code arr = {7, 3, 8, 1, 5}, the pairs found should be (7, 3),(7, 1),(7, 5),(3, 1),(8, 1),(8, 5) and the total number of pairs is 6.

The task is to create the code with time complexity of O(n log n) but big O still confuses me. I'm not sure if this is O(n^2) and not sure if the program will slow down with bigger arrays.

public class Test {
    public static void main(String[] args) {
        int[] arr = {7, 3, 8, 1, 5};
        System.out.println();
        System.out.println("The number of pairs is " + countPair(arr));
    }
    public static int countPair(int[] arr) {
        int i = 0, j = 1;
        int ctr = 0;
        int len = arr.length;
        while (i < len) {
            if (j == len) {
                i++;
                j = 1;
            }
            else if (i < j && (arr[i] > arr[j])) {
                ctr++; // Counting pairs
            }
            j++;
        }
        return ctr;
    }
}

Output:

The number of pairs is 6

What's your algorithm? Separate code from design and you can understand Big O . — nicomp, Oct 03 '21 at 15:12
you have `O(n^2)` complexity, simply count the number of times, the program executes in your code : it's 5,4,3,2,1 , or n , n -1 , n-2 .... 1 -> which can be simplified to n*(n-1) which means O(n^2) — tsamridh86, Oct 03 '21 at 15:18
not giving the final solution, as you should figure this out yourself, best of luck — tsamridh86, Oct 03 '21 at 15:19

Task is to create a code in O(n log n), what is the time complexity of this code that I wrote?

0 Answers0