# median of medians 證明
* 感謝410410101 雷子頡同學與我共同討論
## 為甚麼要分成5個一組?
1. 我發現投影片上的公式在分成組數不一樣的情況下，最後一項的O(n)會不同
-> 所以我假設分成k個一組，嘗試找出general case

2. 改寫投影片上的公式，使其與k有關聯

計算後的函數圖形長這樣

-> 可以發現，k其實越小越好

3. 那為甚麼不分成3個一組呢?

-> 根據證明，k=3時時間複雜度根本不是O(n)，也就不考慮了(1個一組的同理)

4. 這邊補上7個一組的情況，可以看到也是O(n)等級的

## 結論
當分成的組數(k)不一樣的時候，投影片證明時的d會變。在k=1,3的情況下，時間複雜度可以被證明不是O(n)等級；而在最極限的k=n時，dn甚至來到nlog(n)等級，所以最佳解的確是5個一組的情況