4 ms·

You lost me at (6): Shouldn't it be proportional to O(n log 100) ~ 0(n) aka linear time?

• NY_Entrepreneur 15y ago
  Yup! I typed too fast! You are correct. I was thinking the right thing but typing the wrong thing! I'm too used to typine (n)ln(n)!. So, sure, worst case, n times have to do a heap 'sift' which is time proportional to ln(100) as you said. Short answer: I blew it! But for the exercise, that is, when there are no ties among the n numbers and all permutations are equally probable, for 100 < m < n, the probability that number m is among the 100 largest so far and, thus, causes a heap 'sift', seems to be 100/m. So, the expected work on number m is proportional to just (m - 100)/m + ln(100) (100/m), first cut, wild guess, don't hold me to it! So, sum this on m and get the expected work (computational time complexity) up to a constant of proportionality. Maybe! That is, so far, first cut, the exercise looks simple! When do the sum, I smell a ln(n) term!