O(NlogN) algorithm runs faster than O(n)... wait, what?

Question

I am a bit confused, to be honest. I was working out the one of the classical algorithm problems. Given a collection of integers, find if are there 2 elements summing to a given number.

So I have implemented 2 solutions.

bool find1(std::vector<int>& V, int sum) 
{
    std::unordered_set<int> hashTable;
    for (int i = 0; i < V.size(); ++i) 
    {
        if (hashTable.find(V[i]) != hashTable.end()) 
        {
            return true;
        }
        hashTable.insert(sum - V[i]);
    }
    return false;
}

bool find2(std::vector<int>& V, int sum) 
{
    for (int i = 0; i < V.size() ; ++i) 
    {
        if (std::binary_search(V.begin(), V.end(), sum - V[i])) 
        {
            return true;
        }
    }
    return false;
}

Find1 is expected to be a linear algorithm (depending on the load of buckets and efficiency of hashing function).

Find2 is expected to be NlogN, we loop and do a binary search for every iteration.

After implementing this function I tried to test the running times of these algos on a relatively big collection, and the result confused me..

int main() 
{
    std::vector<int> V(10000,0);

    std::chrono::system_clock::time_point now1 = std::chrono::system_clock::now();

    for (int i = 0; i < 100; ++i) 
    {
        bool b = find1(V, 1000);
    }

    std::chrono::system_clock::time_point then1 = std::chrono::system_clock::now();
    std::cout <<"Linear with hashing = "<< std::chrono::duration_cast<std::chrono::microseconds>(then1 - now1).count()<<std::endl;

    std::chrono::system_clock::time_point now2 = std::chrono::system_clock::now();
    std::sort(V.begin(), V.end());
    for (int i = 0; i < 100; ++i)
    {
        bool b = find2(V, 1000);
    }

    std::chrono::system_clock::time_point then2 = std::chrono::system_clock::now();
    std::cout <<"NlogN with binary_search = " <<std::chrono::duration_cast<std::chrono::microseconds>(then2 - now2).count() << std::endl;

    system("pause");
}

Here I initialize the vector with 0s to be sure that both algos run the worst case.
The output of the program is:

Linear with hashing = 6759245         
NlogN with binary_search = 4508025

How this is possible? Can anyone please explain this to me?

You do not only search for an element in `Find1` but also insert an element. Additionally you do IO operations which is probably an overhead. Have you tried to run it without those operations? — BluesSolo, Jul 23 '18 at 13:38
Why is searching for 1000 in an array of all 0's the worst case for binary search? I'd expect it terminates immediately when it finds the largest value in the array is smaller than 1000. — Paul Hankin, Jul 23 '18 at 13:38
@BluesSolo The IO operations are outside of the timings so they don't participate in the calculations. — NathanOliver, Jul 23 '18 at 13:39
@NathanOliver He had a `std::cout << V[i] << std::endl;` in the method before. Appearently it was deleted just a second ago. — BluesSolo, Jul 23 '18 at 13:40
`V` is already sorted, so `std::sort(V.begin(), V.end());` might be `O(N)`. — Jarod42, Jul 23 '18 at 13:46
Did you enable compiler optimizations for your test case? Your timings seem especially slow. — Blastfurnace, Jul 23 '18 at 13:58
Related: [Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?](https://stackoverflow.com/questions/22594174/can-an-on-algorithm-ever-exceed-on2-in-terms-of-computation-time/22594210#22594210) — Bernhard Barker, Jul 23 '18 at 14:43
For [me it is as expected](https://wandbox.org/permlink/6fi9WEjFAERzjqa3). So more details are needed. Compiler, optimizations, platform. — Marek R, Jul 23 '18 at 15:13

eerorika · Accepted Answer · 2018-07-23T14:50:17.197

Just because the upper bound of the asymptotical complexity of one algorithm is less than another, doesn't mean that it's faster for any arbitrary input. It just means that there exists a certain size of input N', beyond which the less complex algorithm will be faster. This size will be specific to each particular system running the program.

Measuring the asymptotically more complex algorithm to be faster simply means that your test was below the size N'. However, that assumes that your complexity analysis applies to the program in the first place. For example, analyzing the worst case complexity is wrong if your program tests the algorithm with best-case input and vice versa.

For what it's worth, the results of on my system are:

Linear with hashing = 9557
NlogN with binary_search = 15828

score 7 · Answer 2 · edited Jul 24 '18 at 01:35

You create a hashtable without expected size. You then insert elements to it one by one. This causes the hashtable to be resized over and over causing a system call to allocate more memory.

While this is all amortized O(1) per insert the hidden constant for the system call is large enough to make the binary search faster.

Try setting an expected size for the hashtable to sizeof(V) * 1.2 or so to avoid rehashing. If that isn't enough compare the timings with 100000, 1000000, 10000000, ... values. You should see the hashtable winning as N gets larger.

Note: binary search with V.end() == 0 will terminate on the first compare and is not worst case. It's best case. Might be even more reason why it's faster.

score 1 · Answer 3 · answered Jul 23 '18 at 13:45

1

O(N) is asymptotically faster than O(N Log N). That doesn't mean that it is faster.

Review the definition of the Big-O notation.

answered Jul 23 '18 at 13:45

O(NlogN) algorithm runs faster than O(n)... wait, what?

3 Answers3