Some instruction sets are limited to one bit shift per instruction. And some instruction sets allow you to specify any number of bits to shift in one instruction, which usually takes one clock cycle on modern processors (modern being an intentionally vague word). See dan04’s answer about a barrel shifter, a circuit that shifts more … Read more
A useful way to approach these types of problems is by thinking of the recursion tree. The two features of a recursive function to identify are: The tree depth (how many total return statements will be executed until the base case) The tree breadth (how many total recursive function calls will be made) Our recurrence … 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); } }
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
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
Getting a slice is O(i_2 – i_1). This is because Python’s internal representation of a list is an array, so you can start at i_1 and iterate to i_2. For more information, see the Python Time Complexity wiki entry You can also look at the implementation in the CPython source if you want to.
The sum is indeed the worst of the three for Big-O. The reason is that your function’s time complexity is (n) => 3n + nlogn + nlogn which is (n) => 3n + 2nlogn This function is bounded above by 3nlogn, so it is in O(n log n). You can choose any constant. I just … 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
A binary heap over n elements can be created in O(n) time using a clever algorithm and a clever analysis. In what follows I’m just going to talk about how this works assuming that you have explicit nodes and explicit left and right child pointers, but this analysis is still perfectly valid once you compress … Read more
Are you interested in reducing the time complexity or the space complexity ? The average time complexity can be reduced O(n + d^2), where n is the length of the longer string and d is the edit distance. If you are only interested in the edit distance and not interested in reconstructing the edit sequence, … Read more