Searching for an element in a heap of size N is not O(K). First, it does not make sense that the time complexity for finding one element depends on the number of elements you are trying to extract (which is what K represents). Also, there is no such thing as searching in a heap — … 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
I benchmarked it for you: CodePad Your intuition on this was correct! $test=array(); for($run=0; $run<1000; $run++) $test[]=rand(0,100); $time=microtime(true); for($run=0; $run<100; $run++) $out=array_unique($test); $time=microtime(true)-$time; echo ‘Array Unique: ‘.$time.”\n”; $time=microtime(true); for($run=0; $run<100; $run++) $out=array_keys(array_flip($test)); $time=microtime(true)-$time; echo ‘Keys Flip: ‘.$time.”\n”; $time=microtime(true); for($run=0; $run<100; $run++) $out=array_flip(array_flip($test)); $time=microtime(true)-$time; echo ‘Flip Flip: ‘.$time.”\n”; Output: Array Unique: 1.1829199790955 Keys Flip: 0.0084578990936279 Flip … Read more
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
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
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 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
This seems to be a question of mislead, because I happened to read that book just now. This part of text in the book is a typo! Here is the context: =================================================================== Question: What is the running time of this code? 1 public String makeSentence(String[] words) { 2 StringBuffer sentence = new StringBuffer(); 3 for … Read more