3 ms·
The linked proof for that median of medians is O(n) feels counterintuitive to me. Here's a (simpler?) alternative. T(0) = 0 T(1) = 1 T(n) = n + T(n/5) +
by melonmouse 2y ago
The linked proof for that median of medians is O(n) feels counterintuitive to me. Here's a (simpler?) alternative.
T(0) = 0
T(1) = 1
T(n) = n + T(n/5) + T(7/10*n)
We want to prove that:
T(n) ≤ C*n
It is intuitive that T(a+b) ≥ T(a) + T(b), or in other words, T is superadditive. That can be shown by induction:
Induction base: it holds for all a+b < 1, the only case being a=0, b=0:
T(0+0) = 0 + T(0) + T(0) ≥ T(0) + T(0)
Induction step: suppose it holds for all a+b < k. Let a+b = k.
T(a+b) = T(k)
= k + T(k/5) + T(7/10*k)
≥ k + T(a/5) + T(b/5) + T(7/10*a) + T(7/10*b)
= [a + T(a/5) + T(7/10*a)] + [b + T(b/5) + T(7/10*b)]
= T(a) + T(b)
Because T is superadditive:
T(n) = n + T(n/5) + T(7/10*n)
≤ n + T(n/5 + 7/10*n)
= n + T(9/10*n)
Now we can apply the master theorem. Or to write out the proof (using a geometric series):
T(n) ≤ n + T(9/10*n)
≤ n * ∑ᵢ₌₀ᶦⁿᶠᶦⁿᶦᵗʸ (9/10)^i
= n * 1/(1-9/10)
= 10*n
So, we have shown the algorithm is O(n) with C=10 (or less).
- beyondCritics 2y agoI like the idea to use super additivity, but in a proof you cannot creatively extend T to the reals, this should be fixed. Here is the slightly mopped up proof i had in mind, when i posted my hints below: Let be r>=1 and 0<a(i) for all 1<=i<=r and 1/a(1) + ... + 1/a(n) =: s < 1. Then a(i) > 1 for all 1 <= i <= r. Let be c > 0 and T(0) := 0 T(n) := c \* n + T(floor(n/a(1))) + ... + T(floor(n/a(r))) Then T(n) <= b * n for all n with b := c/(1-s) > 0 ! Proof by induction: "n=0" : The statement holds trivially. "k->n": Let n>=1 and assume the statement holds for all 0<=k<n. Now since a(i)>1 we have floor(n/a(i)) <= n/a(i) < n. By the induction hypothesis therefore T(floor(n/a(i))) <= b * floor(n/a(i)) <= b * n/a(i). Apply this to get: T(n) = c * n + T(floor(n/a(1))) + ... + T(floor(n/a(r))) <= c * n + b * n/a(1) + ... + b * n/a(r) = (c + b*s) * n = b * n. Hence T(n) <= b * n.