Is this complexity (for a loop) of spatial 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); } } } 

Will it be O (1) or O (n)? I suppose O (n), but isn't that a reuse of memory space every time it does O (1)?

Answer 1

This is O (1)

Instead of 2 variables of constant size string i and Integer a this method does not allocate any additional space. This means that this loop clearly has constant spatial complexity .ie. O (1) .

To clarify this, I would rather ask you a question:

Do you invoke a (iterative) binary search for an algorithm of spatial complexity O (n)?

Absolutely not.

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

PS : I clarify the doubt raised by the OP in the comments of this answer from here on and on →

As pointed out by MichaelRecachinas, String and Integer in this loop are references. They are not a copy, so they will not contribute to the spatial complexity of this function.

PPS : Integer a and string i are allocated memory only once, and then reused at each iteration of the loop.

Answer 2

Cosmic complexity defines "how much extra space (asymptotically speaking) I use in this piece of code." Here, how spatial complexity analysis will work, showing two common cases (for your code snippet):

Example 1: Step-by-step values ​​of hashtable and list

 // assume `list` and `hashtable` are passed by value public void check_10(List<String> list, HashMap<String, Integer> hashtable) { for (String i : list) { Integer a = hashtable.get(i); if (a > 10) { hashtable.remove(i); } } } 

Assuming that you have N elements in the hashtable and no elements are deleted (i.e. a <= 10 for all N elements), at the end of the loop you will have N elements remaining in the hashtable . In addition, each String in the N keys in the hashtable contains up to S characters. Finally, each Integer in the values ​​of N in the hashtable is constant.

Similarly, you have the possible number of M lines in list , where each String can contain up to S characters.

Finally, Integer a does not contribute to analysis because it refers to memory that has already been accounted for. We can take this Integer a memory Integer a constant.

Therefore, assuming that hashtable and list have been declared in a method, you are looking at the complexity of the O(N*S + M*S + I) space.

However, asymptotically, we do not care about I ( Integer a ), because it is a constant size, which is probably much smaller than N and M Similarly, S is probably much smaller than N and M This means that the complexity of the space is O(N + M) . Since both are linear terms, we can (carefully) reduce this to O(n) , where N is the linear term, which is a linear combination of N and M

Example 2: Passing by reference hashtable and list or in another declaration (as in your example)

 // assume `list` and `hashtable` are passed by reference or // declared elsewhere in the class as in // // public void check_10() { public void check_10(List<String> list, HashMap<String, Integer> hashtable) { for (String i : list) { Integer a = hashtable.get(i); if (a > 10) { hashtable.remove(i); } } } 

In this method, list and hashtable already allocated elsewhere, which means that the complexity of the space for this method is O(1) , because we only use constant space in Integer a and String i (even though technically they are references to previously allocated memory - you can consider the constant space as a result of storing the link).

but does he repeat the memory location every time doing this O (1)?

It depends on what you mean by "reuse" of memory space. Theoretically, the analysis of spatial complexity does not exactly consider the details of the implementation of the language in this sense. This means that if you had a loop like

 for (int i = 0; i < N; i++) { T myvar = new T(); } 

you do not consider the consequences of what happens to myvar after each iteration of the loop. By the “consequences of what happens” I mean, does the garbage collector collect memory after each iteration, or do you constantly allocate N memory spots on the heap? In the case of GC, this will be O(1) as you are reusing memory. In the case of an “infinite” distribution, this will be O(n) , since now you have N spots highlighted. Again, theoretically this is usually not considered in the analysis, and any T myvar = new T() usually considered O (1) regardless of whether it sits in a loop or not.

In general, if you mean reusing the same memory location for list and hashtable each iteration, the answer is simpler. Consider the following:

 public void foo() { int list[] = {1, 2, 3, 4}; for (int i = 0; i < list.length; i++) { System.out.println(list[i]); } } 

Despite the fact that list declared only once, and we only iterate through list and print the contents, foo() is still O (n) in memory complexity, because we allocated list , where in the asymptotic one it can have up to N elements. Therefore, regardless of whether it uses the same or different spots in the memory, they both still contribute to linear spatial complexity.

TL; DR

However, in your particular case, both list and hashtable have already been allocated elsewhere in the program and are not presented here, so they do not contribute to complexity, and Integer a and String i are only constant in memory. Therefore, this method will be O(1) .

Answer 3

This is the complexity of the O (n) space, because the list occupies this space. :). A hash table has at most O (n), so the sum of spatial complexity is still O (n).