CODEWITHSUNDEEP
c++visual-studio-2015big-otime-complexitypriority-queue
AlwaysMoving
AlwaysMoving

Reputation: 63

Time complexity of priority_queue::push() in Visual Studio?

I use Windows and Visual Studio 2015. As far as I can see from references and others' questions, priority_queue::push() should have O(log(n)) time complexity. This means of course that this simple code:

#include <queue>
using namespace std;
int main()
{
    priority_queue<int> q;
    const int n=100000; //We can vary this
    for (int i = 0; i < n; i++)
    {
        q.push(i);
    }
}

should have complexity O(nlog(n)), which means for n=100 000 as above it should be piece of cake. It takes several minutes for me (the same thing with std::set takes just a second).

I have debugged this code and stopped it at multiples of 10 seconds, and plotted the squares of i for those times. They very (!) accurately lie on a line, which would mean the above code has complexity of O(n^2).

My question is, is not priority_queue::push() guaranteed to run in O(log(n)) or am I doing something very wrong?

Thanks in advance!

EDIT: I have tried the tip in this post. It didn't improve things, so I suppose reallocating the underlying container is not my issue.

EDIT: SOLVED As usual the answer is very simple. I had run the program in debug mode, which apparently changes the complexity of some functions. I was not aware of this, though I suppose it is quite reasonable...

Upvotes: 2

Views: 831

Answers (2)

Puppy
Puppy

Reputation: 146998

The answer is no, it is not guaranteed to run in O(log(n)) at all. That guarantee would be impossible to implement.

Upvotes: 2

Danny_ds
Danny_ds

Reputation: 11406

Several minutes for n=100000 seems like a very long time.

Are you by any chance testing in debug mode?

About complexity and performance:

From std::priority_queue:

Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains

And:

By default, if no container class is specified for a particular priority_queue class instantiation, the standard container vector is used.

Which would mean that in a loop where i gets incremented, the new item needs to be inserted at the beginning of the vector, meaning that all other elements have to be shifted one - this for each iteration. Since all elements in vector are stored contiguously (while push_back is actually used to insert the items, push_heap is called to rearrange them).

Turning that around (using the default vector container) almost takes no time, even in debug mode.

From Are std::vector elements guaranteed to be contiguous?:

23.2.6 Class template vector [vector]

1 A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously, meaning that if v is a vector where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

A solution could be to specify a different container type:

template <class T, class Container = vector<T>

So, as for complexity of O(log(n)) for priority_queue::push(), it would be hard to guarantee that, since the underlying container type can differ, and each has it's own implementation for inserting/rearranging items. But O(log(n)) would be the best possible scenario.

But perhaps even more important is the time each operation takes, apart from the complexity factor.

EDIT (question): I have tried the tip in this post. It didn't improve things, so I suppose reallocating the underlying container is not my issue.

It's not so much about reallocating memory for storage of the elements (vector will do that in blocks anyway - although for larger containers preallocation is always desirable), but about inserting eacht element before the first one (if that is really the case, which seems to be so). Even if enough space is allocated, to insert an element in front in a vector, all other elements need to be moved exactly one element-size. It's that moving that takes time.

Upvotes: 1

Related Questions