Is this function (for loop) space complexity O(1) or O(n)?

Question

public void check_10() {
    for (string i : list) {
        Integer a = hashtable.get(i);
        if (a > 10) {
            hashtable.remove(i);
        }
    }
}

Would this be O(1) or O(n)? I'm guessing O(n), but isn't it reusing the spot of memory a each time making it O(1)?

Answer 1

It is O(1)

Other than 2 constant sized variables string i and Integer a this method does not allocate any extra space. Which means this loop clearly has constant space complexity .ie. O(1).

To clarify it further, I would rather ask you a question :

Do you call (iterative)binary search an O(n) space complexity algorithm ?

Absolutely not.

Your function check_10() uses a preallocated list and hash table (just like iterative binary search uses preallocated sorted array) and 2 constant space variables so it has O(1) space complexity.

PS : I am clarifying the doubt raised by OP in comments of this answer from here onwards ->

As pointed out by MichaelRecachinas, String and Integer in this loop are references. They are not a copy so they won't contribute anything to the space complexity of this function.

PPS: Integer a and String i are allocated memory only once and then are reused in each iteration of the loop.