> 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)?