CODEWITHSUNDEEP
arraysalgorithmspace-complexity
Lame Things
Lame Things

Reputation: 61

What's the space complexity after you modify the given array?

Consider any problem, and in the input you are given an array of size n. And in that problem you are allowed to modify the array. So, suppose you solved the problem that was asked in O(n) time and also you didn't used any extra space apart from modifying the given array. So, will that modification of the given array will be considered as O(n) space complexity?? Or the space complexity is still constant as you haven't used any extra space apart from modifying the given array?

Upvotes: 2

Views: 1186

Answers (2)

Jeremy Iglehart
Jeremy Iglehart

Reputation: 4479

Yes the Space Complexity is O(n), and the extra space you speak of aka: "Auxiliary Space" is O(1).

Space Complexity of an algorithm is the total space used by an algorithm at run time with respect to the input size.

Always remember: "If you use it, count it." – If your algorithm uses the space, you have to count it in your Space Complexity analysis.

The term Space Complexity is often conflated with the term Auxiliary Space.

Space Complexity = Input + Auxiliary Space

Geeksforgeeks has a really great page about this topic and addresses this issue right at the top of the article:

  • Auxiliary Space is the extra space or temporary space used by an algorithm.
  • Space Complexity of an algorithm is the total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.

By way of explanation in modern Javascript vernacular, if you will:

spaceComplexity = Math.max(input, ...auxiliarySpace);

Here is a concrete example using Selection Sort:

let selectionSort = (array) => {
    for (let i = 0; i < array.length - 1; i++) {
        let indexOfMin = i;
        for (let j = i + 1; j < array.length; j++) {
            if (array[j] < array[indexOfMin]) {
                indexOfMin = j;
            }
        }
        [array[i], array[indexOfMin]] = [array[indexOfMin], array[i]]
    }
};

let input = [4, 1, 5, 2, 3];

selectionSort(input);

console.log(input); // [1, 2, 3, 4, 5]

The input we know takes up O(n) space.

This Selection Sort function:

  • Sorts the array in place without creating a copy of the input array

  • Only creates 3 extra variables for iterating [i, j] and bookkeeping indexOfMin. So the amount of extra space created in relation to the input n is constant. If n=10 you still only create 3 extra variables, and if n=10,000 still, only 3 variables to sort the array.

  • Time Complexity = O(n^2)

  • Auxiliary Space = O(1) = [i, j, indexOfMin].length // 3

    a constant of 3 simplifies to 1 for Big-O notation

  • Space Complexity = O(n)

    Because:

    Space Complexity = Input + Auxiliary Space

    Space Complexity = O(n) + O(1)

    O(n) + O(1) simplifies to just O(n) in Big-O notation

I believe the term Space Complexity gets thrown around in places that it shouldn't because "if we want to compare standard sorting algorithms on the basis of space, then Auxiliary Space would be a better criterion than Space Complexity. Merge Sort uses O(n) auxiliary space, Insertion sort, and Heap Sort use O(1) auxiliary space. The space complexity of all these sorting algorithms is O(n) though." - quoted from GeeksforGeeks

To drive this point home about how confusing this topic can be for people - referencing my favorite big-o notation site with a great image I use for comparison https://www.bigocheatsheet.com/ it lists Selection Sort as O(1) Space Complexity. Clicking on the reference link takes you to Wikipedia where they say "Worst-case space complexity O(1) auxiliary"

It's an unfortunate conflation because it's an extremely common question, and it's not always understood clearly.

Phrases like "in big O notation describe n as a characteristic of the input influencing space complexity" don't grok immediately for everyone. This can be rephrased to "Space Complexity of an algorithm is the total space used by an algorithm at run time with respect to the input size."

If your function is passed the input and you're using it, maybe iterating over it - then it counts. If it's affecting the space required to work on the input, your Space Complexity will include it. The way I like to think about it is "It's kind of hard to sort something you're not allowed to look at".

Think about it physically. If you have 10,000 pages of a book that blew in the wind and you now have to put them back in order - you're going to need enough space somewhere to lay them out enough to sort them.

Further Related Reading:

Upvotes: 3

suyashpatil
suyashpatil

Reputation: 246

If you are modifying the array then you are using O(1) space. Space complexity is determined as what extra space you have used excluding the variables in the question. In the question, array is already declared and you are just modifying it. You have not created any extra array for it. So all and all, it takes constant space.

Upvotes: -1

Related Questions