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

Question

I have written code for two approaches to find out the first unique character in a string on LeetCode.

Problem Statement: Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Sample Test Cases:

s = "leetcode" return 0.

s = "loveleetcode", return 2.

Approach 1 (O(n)) (correct me if I am wrong):

class Solution {
    public int firstUniqChar(String s) {

        HashMap<Character,Integer> charHash = new HashMap<>();

        int res = -1;

        for (int i = 0; i < s.length(); i++) {

            Integer count = charHash.get(s.charAt(i));

            if (count == null){
                charHash.put(s.charAt(i),1);
            }
            else {
                charHash.put(s.charAt(i),count + 1);
            }
        }

        for (int i = 0; i < s.length(); i++) {

            if (charHash.get(s.charAt(i)) == 1) {
                res = i;
                break;
            }
        }

        return res;
    }
}

Approach 2 (O(n^2)):

class Solution {
    public int firstUniqChar(String s) {

        char[] a = s.toCharArray();
        int res = -1;

        for(int i=0; i<a.length;i++){
            if(s.indexOf(a[i])==s.lastIndexOf(a[i])) {
                res = i;
                break;
            }
        }
        return res;
    }
}

In approach 2, I think the complexity should be O(n^2) since indexOf executes in O(n*1) here.

But when I execute both the solutions on LeetCode I get runtime 19 ms for approach 2 and 92 ms for approach 1. I am confused; why does that happen?

I suppose LeetCode tests for both small and large input values for best, worst and average cases.

Update:

I am aware of the fact that O(n^2 algorithms) can perform better for certain n < n1. In this question I wanted to understand why that is happening in this case. i.e. which part of Approach 1 makes it slower.

LeetCode link to the question

Answer 1

Consider:

• f₁(n) = n²
• f₂(n) = n + 1000

Clearly f₁ is O(n²) and f₂ is O(n). For a small input (say, n=5), we have f₁(n) = 25 but f₂(n) > 1000.

Just because one function (or time complexity) is O(n) and another is O(n²) doesn't mean that the former is smaller for all values of n, just that there is some n beyond which this will be the case.

Answer 2

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.

Answer 3

Big O notation is a theoretical measure of the manner in which an algorithm scales in terms of memory consumption or computational time with N - the number of elements or dominant operations, and always as N->Infinity.

In practice, N in your example is fairly small. Whilst adding an element to a hash-table is generally considered to be amortised O(1), it might also result in a memory allocation (again, depending on the the design of your hash-table). This may not be O(1) - and may also result in the process making a system call to the kernel for another page.

Taking the O(n^2) solution - the string in a will quickly find itself in cache and will likely run uninterrupted. The cost of a single memory allocation will likely be higher than the pair of nested loops.

In practice with modern CPU architectures, where reads form cache are orders of magnitude faster than those from main memory, N will be quite large before using a theoretically optimal algorithm outperforms a linear data structure and linear searching. Binary trees are particularly bad news for cache efficiency.

[Edit] it's Java: The hash table contains references to boxed java.lang.Character object. Every single addition will result in a memory allocation

Answer 4

O(n²) is only the worst case time complexity of the second approach.

For strings such as bbbbbb...bbbbbbbbbaaaaaaaaaaa...aaaaaaaaaaa where there are x b's and x a's, each loop iteration takes about x steps to determine the index, hence the total performed steps is about 2x2. For x about 30000, it would take about 1~2 second(s), while the other solution would perform much better.

On Try it online, this benchmark computes that approach 2 is about 50 times slower than approach 1 for the string above. For larger x, the difference is even larger (approach 1 takes about 0.01 second, approach 2 takes a few seconds)

However:

For strings with each character chosen independently, uniformly from {a,b,c,...,z} ^[1], the expected time complexity should be O(n).

This is true assuming Java uses the naive string searching algorithm, which searches the character one-by-one until a match is found, then immediately returns. The time complexity of the search is the number of considered characters.

It can be easily proven (the proof is similar to this Math.SE post - Expected value of the number of flips until the first head) that the expected position of a particular character in a uniform independent string over the alphabet {a,b,c,...,z} is O(1). Therefore, each indexOf and lastIndexOf call runs in expected O(1) time, and the whole algorithm takes expected O(n) time.

^[1]: In the original leetcode challenge, it is said that

You may assume the string contain only lowercase letters.

However, that is not mentioned in the question.

Answer 5

Karol already provided a good explanation for your special case. I want to add a general remark regarding the big O notation for time complexity.

In general this time complexity doesn't tell you too much about the actual performance. It just gives you an idea of the number of iterations needed by a particular algorithm.

Let me put it like this: if you execute a huge amount of fast iterations this can still be faster than executing very few extremely slow iterations.

Answer 6

First, complexity analysis does not tell you an awful lot. It used to tell you how algorithms would -- in theory -- compare as the size of the problem grows to large numbers (towards infinity, if you will), and to some extent it still does.
However, complexity analysis makes assumptions that were only half-true some 30-40 years ago and are not in any way true nowadays (such as e.g. all ops are the same, all accesses are the same). We live in a world in which constant factors are huge, and not all operations are the same, not even remotely. Insofar, it has to be considered with very great care, in no case can you assume "this is O(N) so it will be faster". That's a huge fallacy.

For small numbers, looking at "big O" is mostly pointless, but even for large numbers, be aware that the constant factor can play a huge, dominating role. No, the constant factor is not zero, and it is not negligible. Do not ever assume that.
The theoretically super awesome algorithm which, for example, finds something in a billion elements with only 20 accesses can be much slower than a "bad" algorithm that takes 200,000 accesses -- if in the first case each of the 20 accesses causes a page fault with a disk seek (each of which is worth some hundred million operations). Theory and practice do not always go hand in hand here.

Second, despite being idiomatic and generally looking like a good idea (it's O(1), eh?), using a hash map is just bad in many cases. Not in every case, but this is such a case. Compare what the two code snippets are doing.

The O(N²) one converts a moderately small string to a character array once (which basically costs zero) and then repeatedly accesses that array in a linear fashion. Which is pretty much the fastest thing a computer is able to do, even in Java. Yes, Java is agnostic of any such thing as memory or caches, but that cannot change the fact that these things exist. Locally accessing small/moderate amounts of data in a mostly linear fashion is fast.

The other snippet inserts characters into a hashmap, allocating a data structure for every character. Yes, dynamic allocations in Java are not that expensive, but still, allocations are nowhere near free, and memory accesses become non-contiguous.
Then, a hash function is calculated. This is something that is often overlooked with hash maps. For a single character, this is (hopefully) a cheap operation, but it is nowhere near free^[1]. Then, the data structure is in some way inserted into a bucket (which is technically nothing but another non-coherent memory access). Now, there's a fair chance of a collision, in which case something else must be done (chaining, rehashing, whatever).
Later, values are being read from the hashmap again, which again involves calling the hash function, looking up the bucket, possibly traversing a list, and doing a comparison at each node (this is necessary due to the possibility of collisions).

Every operation thus involves at least two indirections, plus some calculations. That, all in all, is painfully expensive compared to just iterating over a small array a couple of times.

---

^[1] Not an issue here for single-character keys but still, fun fact: People often talk of hash maps in terms of O(1) which already isn't true with e.g. chaining, but are then surprised that actually hashing the key is O(N) in respect of the length of the key. Which may very well be noticeable.

Answer 7

I've ported the functions to C++(17) to see if the difference was caused by algorithm complexity or Java.

#include <map>
#include <string_view>
int first_unique_char(char s[], int s_len) noexcept {
    std::map<char, int> char_hash;
    int res = -1;
    for (int i = 0; i < s_len; i++) {
        char c = s[i];
        auto r = char_hash.find(c);
        if (r == char_hash.end())
            char_hash.insert(std::pair<char, int>(c,1));
        else {
            int new_val = r->second + 1;
            char_hash.erase(c);
            char_hash.insert(std::pair<char, int>(c, new_val));
        }
    }
    for (int i = 0; i < s_len; i++)
        if (char_hash.find(s[i])->second == 1) {
            res = i;
            break;
        }
    return res;
}
int first_unique_char2(char s[], int s_len) noexcept {
    int res = -1;
    std::string_view str = std::string_view(s, s_len);
    for (int i = 0; i < s_len; i++) {
        char c = s[i];
        if (str.find_first_of(c) == str.find_last_of(c)) {
            res = i;
            break;
        }
    }
    return res;
}

The result was:

The second one is ~30% faster for leetcode.

Later, I noticed that

    if (r == char_hash.end())
        char_hash.insert(std::pair<char, int>(c,1));
    else {
        int new_val = r->second + 1;
        char_hash.erase(c);
        char_hash.insert(std::pair<char, int>(c, new_val));
    }

could be optimized to

    char_hash.try_emplace(c, 1);

Which also confirms that complexity is not only the only thing. There's "input length", which other answers have covered and lastly, I noticed that

Implementation also makes a difference. Longer code hides optimization opportunities.