Time-complexity of mergesort with alternative merge-function

user_12784355 0
Viewed 75

I currently have this code:

public static void main(String[] args) throws FileNotFoundException {
    Scanner sc = new Scanner(new File(args[0]));
    int amount = sc.nextInt();
    int[] array = new int[amount];

    for (int i = 0; i < amount; i++) {
        array[i] = sc.nextInt();
    }

    System.out.println("FINAL ANSWER " + find(array, 0, array.length - 1));
}


static int find(int arr[], int l, int r) {
    int answer = 0;
    if (l < r) {
        int m = (l + r) / 2;

        int a = find(arr, l, m);
        int b = find(arr, m + 1, r);

        answer = a + b + answer(arr, l, m, r);
    }
    return answer;
}


static int answer(int arr[], int l, int m, int r) {
    int ans = 0;
    for (int i = m; i < r; i++) {
        for (int j = l; j < m + 1; j++) {

            if (arr[i + 1] > arr[j]) {
                ans++;

            }
        }
    }

    return ans;
}

I know mergesort has a time-complexity of O(nlog(n)), however I've replaced the merge-function by a function with two for-loops. So is it now O(n^2) since l, m and r depend on n?

mergesort big-o time-complexity java
1 Answers

The function answer has a complexity of O( (r-m) * (m+1-l) ). The outer for-loop goes from m to r, thus r-m iterations. The inner for-loop goes from l to m+1, so m+1-l iterations.

Given the worst case l=0,r=n and m=n/2, the function can be approximated to O(n^2).

However you need to add the runtime of the function find. So the overall time complexity will be:

  • O(n^2 * log(n)).
user_84847830
Related