In C++11 it is required that for any standard container the .size() operation must be complete in “constant” complexity (O(1)). (Table 96 — Container requirements). Previously in C++03 .size() should have constant complexity, but is not required (see Is std::string size() a O(1) operation?). The change in standard is introduced by n2923: Specifying the complexity … Read more
According to Python wiki: Time complexity, set is implemented as a hash table. So you can expect to lookup/insert/delete in O(1) average. Unless your hash table’s load factor is too high, then you face collisions and O(n). P.S. for some reason they claim O(n) for delete operation which looks like a mistype. P.P.S. This is … Read more
It is reasonable to expect that you cannot do any better than O(N log N) in running time. However, the interesting part is to investigate whether you can sort it in-place, stably, its worst-case behavior and so on. Simon Tatham, of Putty fame, explains how to sort a linked list with merge sort. He concludes … Read more
Starting from root node and moving downwards if you find any node that has either p or q as its direct child then it is the LCA. (edit – this should be if p or q is the node’s value, return it. Otherwise it will fail when one of p or q is a direct … Read more
Leverage negative lookahead: >>> import re >>> x=r'(?!x)x’ >>> r=re.compile(x) >>> r.match(”) >>> r.match(‘x’) >>> r.match(‘y’) this RE is a contradiction in terms and therefore will never match anything. NOTE: In Python, re.match() implicitly adds a beginning-of-string anchor (\A) to the start of the regular expression. This anchor is important for performance: without it, the … Read more
I assume that you are looking for intuitive definitions, since the technical definitions require quite some time to understand. First of all, let’s remember a preliminary needed concept to understand those definitions. Decision problem: A problem with a yes or no answer. Now, let us define those complexity classes. P P is a complexity class … Read more
There are very, very few guarantees, but there are a few optimizations: Extension methods that use indexed access, such as ElementAt, Skip, Last or LastOrDefault, will check to see whether or not the underlying type implements IList<T>, so that you get O(1) access instead of O(N). The Count method checks for an ICollection implementation, so … Read more
Is it a fair assumption that in v8 implementation retrieval / lookup is O(1)? Yes. V8 uses a variant of hash tables that generally have O(1) complexity for these operations. For details, you might want to have a look at https://codereview.chromium.org/220293002/ where OrderedHashTable is implemented based on https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables.
I think there are several questions buried in this topic: How do you implement buildHeap so it runs in O(n) time? How do you show that buildHeap runs in O(n) time when implemented correctly? Why doesn’t that same logic work to make heap sort run in O(n) time rather than O(n log n)? How do … Read more
Remember that log(n!) = log(1) + log(2) + … + log(n-1) + log(n) You can get the upper bound by log(1) + log(2) + … + log(n) <= log(n) + log(n) + … + log(n) = n*log(n) And you can get the lower bound by doing a similar thing after throwing away the first half … Read more