It is certainly not possible with a plain singly-linked list. Sketch proof: to examine the last node of a singly-linked list, we must perform n-1 operations of following a “next” pointer [proof by induction on the fact that there is only one reference to the k+1th node, and it is in the kth node, and … Read more
There you go. This is probably the most trivial example of a function that runs in O(n!) time (where n is the argument to the function): void nFacRuntimeFunc(int n) { for(int i=0; i<n; i++) { nFacRuntimeFunc(n-1); } }
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
One important thing most people forget when talking about Big-O, thus I feel the need to mention that: You cannot use Big-O to compare the speed of two algorithms. Big-O only says how much slower an algorithm will get (approximately) if you double the number of items processed, or how much faster it will get … 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
The purpose of the Big-O notation is to find what is the dominant factor in the asymptotic behavior of a function as the value tends towards the infinity. As we walk through the function domain, some factors become more important than others. Imagine f(n) = n^3+n^2. As n goes to infinity, n^2 becomes less and … Read more
map, set, multimap, and multiset These are implemented using a red-black tree, a type of balanced binary search tree. They have the following asymptotic run times: Insertion: O(log n) Lookup: O(log n) Deletion: O(log n) hash_map, hash_set, hash_multimap, and hash_multiset These are implemented using hash tables. They have the following runtimes: Insertion: O(1) expected, O(n) … Read more
Big-O is an upper bound. Big-Theta is a tight bound, i.e. upper and lower bound. When people only worry about what’s the worst that can happen, big-O is sufficient; i.e. it says that “it can’t get much worse than this”. The tighter the bound the better, of course, but a tight bound isn’t always easy … Read more
Is there anything in the JavaScript guaranteeing that the values are looked up in O(1) time? No. JavaScript does not give any complexity guarantees whatsoever, except for ES6 collections. I know the access operator [] gives a seasoned programmer the impression that he’s dealing with an O(1) lookup structure Yes you are, this is a … Read more