i think it should be O(n^2) because to find median it takes O(n). time using partition algo. so O(n^2) for finding medians of all arrays. plus O(n) time for again finding median of medians so total time = O(n^2) + O(n) = O(n^2). ref. ;- finding median of unsorted array https://discuss.codechef.com/questions/1489/find-median-in-an-unsorted-array-without-sorting-it