3 ms·
This is not correct as written: "But we have k < N, so if we are O(N) we are also O(k) or better."
by asldaslkksdj 11y ago
This is not correct as written: "But we have k < N, so if we are O(N) we are also O(k) or better."
- anonymoushn 11y agoThat's right. We can fix it up though. The E(t_i) we care about are bounded above by a constant (2), so the sum of k such expectations is linear in k. For the cases where k > n/2, the "full table scan" portion is of course also linear in k.
- ridiculous_fish 11y agoNice save! FWIW, here's the fix I wrote up before I saw yours. Yours is much better ;) We only need to consider values in the range 0 < k <= N/2. If k > N/2, we "pick the losers instead of winners" and that reduces k to that range. The expected time E to pick k out of N, is N times the last k terms of H(N): E(k) = N * (H(N) - H(N-k)) Applying the asymptote: E(k) ~ N * (γ + ln(N) - γ - ln(N-k)) = N * (ln(N) - ln(N-k)) We wish to determine its behavior as a function of k. Taking the derivative: dE/dk ~ N/(N - k) which is positive and bounded above by 2 for 0 < k <= N/2: dE/dk <= 2 Using the fact that E(1) = 1, we have: E(k) <= 2k So E cannot be worse than linear in k.