java - Why does this O(n^2) code execute faster than O(n)?

Question

(This question already has answers here): question from:https://stackoverflow.com/questions/53356246/why-does-this-on2-code-execute-faster-than-on

Answer 1

For very short strings e.g. single character the cost of creating HashMap, re-sizing it, looking up entries while boxing and unboxing of char into Character might overshadow the cost of String.indexOf(), which is probably considered hot and inlined by JVM either way.

Another reason might be the cost of RAM access. With additional HashMap, Character and Integer objects involved in a lookup there might be need for additional access to and from RAM. Single access is ~100 ns and this can add up.

Take a look at Bjarne Stroustrup: Why you should avoid Linked Lists. This lecture illustrates that performance is not the same as complexity and memory access can be a killer for an algorithm.