I dont find this code time complexity? O(n)?

Question

I wrote a code that finds the median value of an unsorted array. What is this code's big O? Can you explain? Can we optimize runtime complexity?

public static int medianElement(int[] array,int low, int high) {
    int[] tmpArray = new int[high - low + 1];
    for (int i = 0; i < high - low; i++) {
        tmpArray[i] = array[low + i];
    }

    boolean changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < high - low; i++) {
            if (tmpArray[i] > tmpArray[i + 1]) {
                changed = true;
                swap(tmpArray, i, i + 1);
            }
        }
    }

    return tmpArray[(high - low + 1) / 2];
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

What is the interest of the parameter `size`? It is not used in `medianElement` — 0009laH, Nov 19 '22 at 00:03

score 1 · Accepted Answer · answered Nov 18 '22 at 23:09

1

Your sorting algorithm is called Bubble sort https://en.wikipedia.org/wiki/Bubble_sort. Its runtime is O(n^2) in the worst case and O(n) in the best case.

To improve the average time this code takes to run, you could use a sorting algorithm with better worst case performance, such as merge sort https://en.wikipedia.org/wiki/Merge_sort. Merge sort performs at O(n log n) in the worse case.

answered Nov 18 '22 at 23:09

James Williams

724
6
20

but I didn't use for inside for. – programmer Nov 19 '22 at 09:42
1

Your `while(changed)` is effectively another `for`, given that it will be true and loop `n` times (in the worst case). – James Williams Nov 19 '22 at 09:58

I dont find this code time complexity? O(n)?

1 Answers1