0
$\begingroup$

I have the following implementation of Bubble sort where it calls a helper method named swap.

    public static int[] bubbleSort(int[] array) {
        boolean didSwap = true;
        int j;
        int unsortedUntilIndex = array.length - 1;
    
        // i goes from 0 to array.length - 2
        // j goes from 1 to array.length - 1
        while (didSwap) {
            didSwap = false;
            // for arrays of size 0 or 1 this for loop will never execute
            for (int i = 0; i < unsortedUntilIndex; i++) {
                j = i + 1;
                if (array[i] > array[j]) {
                    swap(i, j, array);
                    didSwap = true;
                }
            }
            unsortedUntilIndex -= 1; // shortens iterations as numbers at highest indices settle into place with each iteration
        }
        return array;
    }
    
    public static void swap(int i, int j, int[] array) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

It seems to me that by simply removing the helper method and including its code inline in the main method, I can reduce the space complexity from O(N) to O(1) since I'd no longer be adding method calls onto the call stack. Am I interpreting this correctly?

$\endgroup$
2
$\begingroup$

The function swap is not recursive so the depth of the call stack is always constant. While it is true that the space complexity of your algorithm is $O(n)$, it is also true that it is $O(1)$ (if we don't count the size needed for the input array array).

Inlining the function swap makes no difference as far as the asymptotic space complexity is considered.

$\endgroup$
2
  • $\begingroup$ it is not $O(1)$ if we don't count the input. Since the for loop goes through the entire array, the minimum size that i needs is at least $\Omega(\log(n))$. Hence, the space complexity is actually $\Omega(\log(n))$ $\endgroup$
    – nir shahar
    Sep 20 at 21:38
  • $\begingroup$ Depends if you are using the uniform cost model or the logarithmic cost model. In the uniform cost model you assume that numbers fit in a single word of memory and you count the number of used memory words. In the logarithmic cost of model the space is indeed $\Omega(\log n)$ (but, e.g., the time would also be $\Omega(n^2 \log n)$). $\endgroup$
    – Steven
    Sep 21 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.