If you’re using C++11, you have access to the <unordered_map> and <unordered_set> headers. These provide classes std::unordered_map and std::unordered_set. If you’re using C++03 with TR1, you have access to the classes std::tr1::unordered_map and std::tr1::unordered_set, using the same headers (unless you’re using GCC, in which case the headers are <tr1/unordered_map> and <tr1/unordered_set> instead). In all cases, … Read more
The running time is O(NW) for an unbounded knapsack problem with N items and knapsack of size W. W is not polynomial in the length of the input though, which is what makes it pseudo-polynomial. Consider W = 1,000,000,000,000. It only takes 40 bits to represent this number, so input size = 40, but the … Read more
The build-heap algorithm starts at the midpoint and moves items down as required. Let’s consider a heap of 127 items (7 levels). In the worst case: 64 nodes (the leaf level) don’t move at all 32 nodes move down one level 16 nodes move down two levels 8 nodes move down three levels 4 nodes … Read more
Dig into the CPython source code and visit Objects/listobject.c, you will find the source code for the count() method in there. It looks like this: static PyObject * list_count(PyListObject *self, PyObject *value) { Py_ssize_t count = 0; Py_ssize_t i; for (i = 0; i < Py_SIZE(self); i++) { int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ); if … Read more
There are many ways that you can think about this problem, depending on the constraints of your problem description. If you know for a fact that exactly one element is duplicated, then there are many ways to solve this problem. One particularly clever solution is to use the bitwise XOR operator. XOR has the following … Read more
there is a very detailed table on python wiki which answers your question. However, in your particular example you should use enumerate to get an index of an iterable within a loop. like so: for i, item in enumerate(some_seq): bar(item, i)
Asymptotic complexity (which is what both big-O and big-Theta represent) completely ignores the constant factors involved – it’s only intended to give an indication of how running time will change as the size of the input gets larger. So it’s certainly possible that an Θ(n) algorithm can take longer than an Θ(n2) one for some … Read more
Your problem can be reduced to that of creating all unique permutations of a particular list. Say A and B are the lengths of the strings arr1 and arr2, respectively. Then construct a list like this: [0] * A + [1] * B There exists a one-to-one correspondence (a bijection) from the unique permutations of … Read more
A jump table is used, making the pattern-match a constant time operation. Unfortunately I’m unable to find an up-to-date citation for this, although this page mentions the implementation of Cmm-level switch statements as jump tables, and this old tagging design document uses a case on a Bool as an example, producing a jump table.
Since the big-O notation is not about comparing absolute complexity, but only relative one, O(n+n) is in fact the same as O(n). Each time you double x, your code will take twice as long as it did before and that means O(n). Whether your code runs through 2, 4 or 20 loops doesn’t matter, since … Read more