CODEWITHSUNDEEP
javatime-complexity
Ezra Henley
Ezra Henley

Reputation: 349

Do repeated dereferences increase time complexity?

Suppose I have an if statement like the following

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (map.containsKey(complement) && map.get(complement) != i) {
        return new int[] { i, map.get(complement) };
    }
}

If the if statement evaluates to true, would map.get(complement) get run twice by the program, making it more advantageous to use a variable before this if statement to assign the result of this dereference, or would the compiler/heap (or something) keep this value in memory so that multiple statements like this only get evaluated once? If it gets evaluated twice, would that increase time complexity for something like a hash map here, or do lookups only take O(1) time anyway so it doesn't really matter?

Upvotes: 0

Views: 121

Answers (3)

Andrey Tyukin
Andrey Tyukin

Reputation: 44957

No, the time complexity does not change: the time required for every possible execution path through the if-statement can be upper-bounded by the time required for a lookup, multiplied with factor 3, plus some overhead for all the other constant time-calculations. O(3 * constant_1 + constant_2) is asymptotically still just O(1) for positive constants.

Since there are no guarantees for referential transparency, the compiler will not optimize the three lookups away.

However, the concrete implementations of the hash map could theoretically (possibly, in the future releases) maintain a cache with pre-computed hash codes and their position in the internally stored array for keys that have been recently been passed to contains method.

Another factor to consider is how your hardware handles memory access. It could be, with a sufficiently clever memory manager, that the content of the hash map is "warm" when it is accessed the second time, so that the second and third access don't matter all that much.

Conclusion: no, the asymptotic runtime does not change. Make it correct first. Then profile it. Then optimize it, if necessary.

Upvotes: 0

M. le Rutte
M. le Rutte

Reputation: 3563

As the compiler/JIT has no way to know whether two invocations to a method will yield the same result there is no way to optimize the calls away. Given that any program may be multithreaded it may even be so that without proper synchronization the map is modified between the two calls and the result of the get returns a different object.

Because the get method will return null if you ask for a key that doesn't exist the code can be rewritten as:

for (int i = 0; i < nums.length; i++) {
   int complement = target - nums[i];
   Integer value = map.get(complement);

   if (value != null && value != i) {
       return new int[] { i, value };
   }
}

Upvotes: 1

Zabuzard
Zabuzard

Reputation: 25923

A lookup on HashMap takes O(1).
For time complexity constant factors don't matter, so if you execute a O(1) call twice it will still only be O(1) since O(2) = O(1). So something like

map.get(complement)
map.get(complement)
map.get(complement)
map.get(complement)

Is still in O(1) because you only execute it a constant amount of times, independent of your input variables.

Java itself doesn't optimize the map.get(complement) call, the map could have changed between both calls. At least I don't know a compiler that does, but maybe there are some that analyze your code that deep.

The loop itself is in O(n) for n = nums.length because you have at least the worst case (where the map does not contain the key) where you iterate it completely, yielding O(n) for n = nums.length. Probably also in a typical case since your complement could be anywhere, probably there is no pattern that would make it such that it only yields constant iterations.

And the loop above runs in O(n) too because it executes O(1) statements n-times.

Upvotes: 3

Related Questions