[melonmouse]

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]

I 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.