I understand why, in worst case, where T is the running time of the algorithm, that using the median of medians algorithm with blocks of size three gives a recurrence relation of

> 
> T(n) = T(2n / 3) + T(n / 3) + O(n)
> 
> 
> 

The [Wikipedia article for the median-of-medians algorithm](https://en.wikipedia.org/wiki/Median_of_medians) says that with blocks of size three the runtime is not O(n) because it still needs to check all n elements. I don't quite understand this explanation, and in my homework it says I need to show it by induction. 

How would I show that median-of-medians takes time Ω(n log n) in this case?