Search code examples
c#javac++algorithmcomplexity-theory

Space complexity of bubble sort algorithm


i am trying to do a study on Space complexity of bubble sort algorithm what i know that the Space complexity of bubble sort algorithm is O(1) given the below bubble sort algorithm how can i change the bubble sort aalgorthim code to make the space or memory complexity to O(n) or O(n square) , etc i need to understand where the space complexity playes a role ...thanks

 public void bubbleSort(int[] arr) {
    boolean swapped = true;
    int j = 0;
    int tmp;

    while (swapped) {

        swapped = false;
        j++;

        for (int i = 0; i < arr.length - j; i++) {
            if (arr[i] > arr[i + 1]) {
                tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
                swapped = true;
            }
        }
    }

Solution

  • The space complexity is a measure of how much extra memory your algorithm requires.

    If you were to allocate an extra array of size n (when n is the variable size of the input array), the space complexity would be O(n).