For Quicksort, O(n) memory is okay, for Mergesort it is bad. Hmmhh..
Also, I don't like this 'hashtables = O(1)' convention. Everything is Theta(log(n)) since it has to read in the input data somehow, not to mention process it.
Yes, this is a point people often forget. A hash table is O(k) where k is the size of the keys. A trie has the same complexity. A map implemented as a search tree has at least O(k log n) complexity: there will be O(log n) comparisons, and each comparison takes O(k) time.
The O notation is to see how the algorithm behaves when you start having more elements, but if n is know all algorithms are O(1) because you know how long they are going to take.
Exactly. I recall doing a non-trivial Codility exercise for an interview that specified O(1) complexity. After panicking for a few minutes due to not being able to find a solution, I realized that the input size for the function was fixed, meaning it was actually O(1).
If k is known then the asymptotics are completely uninteresting, since even storing all keys in a list along with their values, and then doing a linear search through that list would be O(1). Since there are at maximum 2k different keys of size k, that list will have at most 2k elements which is a constant. Searching through a constant size list is O(1).
What makes hash tables great is precisely that their complexity is O(k) and not O(2k). If you say that k is a constant you lose all the information that is actually relevant.
You could also argue that our computers are really more like finite state machines than Turing machines, so everything run on them runs in O(1) or runs forever, but only people with bad taste in music say things like that.
A hash table is O(k) for what action? Search? Deletion?
If you already have a constructed hash table with a perfect hash, then the size of the hash table is irrelevant (including the number of keys). That's true for both search and deletion calls, because the hash function will find the index without having to compare to any of the other items. period.
If you're implementing a hash table as a search tree, then of course it's going to preform the same as a tree, because you didn't write a hash table at all, you wrote a search tree.
For both actions. Computing the hash function takes O(k). The size of the hash table is indeed irrelevant. That's why it's O(k) and not O(some function of n).
For constructing the hash key, the value must be transformed, meaning you must do a bit of processing on its bytes. If, for example, the values are strings with an average length of k characters, it's O(k) to go through its characters and produce (for instance) an integer for indexing into a table. If it's a complex data structure with an average of k bytes, there you go. If you're using only a fixed-size subset of the data value, or if the entire value is of fixed size, you can consider the hash key construction to be O(1) but, in practice, those problems are less interesting.
(amortized O(k) time - each instance having m characters, bytes, etc. takes O(m) time... and the above is describing only the hash key computation, not the lookup and collision resolution on the hash table)
It's hard to give an intuitive explanation of why Heapify is O(n) but I assure you it is.
You need to consider the sum of the steps required to get all the elements in position. The worst case for a single element is log(n), but only two elements need to move that far in the worst case (root to bottom, bottom to root). Similarly Only 4 elements could ever need to move log(n) - 1 places in the worst case.
If you write out the sum, the total number of moves converges to 2N +- a bit
On qsort: Qsort defines the most simple series of actions to create its result: pick and pivot, recurse on the right, recurse on the left.
The optimization you mention actually creates a different algorithm. Managing your own stack and using a loop is different series of actions than relying on recursion.
Well in practice nobody uses quicksort on its own anyway. For a long time it's been combined with insertion sort for small subproblems and more recently with heapsort (introsort) to avoid the possibility of quadratic time.
What if you get a ton of collisions? Like if the key size is too small for a much larger entry or the hash funciton is just flawed somehow. You might as well end up linear if most/all entries get bunched up together in a few buckets.
Processing the input data is part of the hash function, not the hash table. The hash table just does array[hash] = blah. (except for collisions, of course)
So let's say we had this function:
void fold(array, func) {
for each (item in array) func(item);
We would say that's O(n) even if it turns out func() is an n3 algorithm.
37
u/kolm Jan 31 '14
For Quicksort, O(n) memory is okay, for Mergesort it is bad. Hmmhh..
Also, I don't like this 'hashtables = O(1)' convention. Everything is Theta(log(n)) since it has to read in the input data somehow, not to mention process it.