Q2a. A heap can be constructed in O(n) time for n inputs. Design an algorithm for finding the k-th smallest element in an unsorted array of length n that is faster than O(n log n) asymptotically. Analyse the complexity of your algorithm assuming k as a constant. I understand where you got to the answer of O(n + klogn). I am confused about why you can't get rid of the constant k, and get: O(n + logn) And then have the dominant n subsume the other factor: O(n). You said "you can only remove a term when you are sure that the other term has asymptotically the same or higher complexity.". Then you said that we can't be sure whether klogn would be asymptotically higher complexity than n. The question states that k is a constant, therefore does it not matter how high the constant is, by the definition of O() that you gave us, are we not certain that n has a higher growth rate than klogn, and in that case, shouldn't we be able to just say it's O(n)?

ANONYMOUS wrote: K is a variable here, not a constant, so we can't do what you have written. K is a constant only for a specific instance. Suppose you have to find n smallest elements? It will be an O(n) algorithm according to your logic. That will break the O(nlog n) lower bound for sorting.