I was reading on Wikipedia about Quicksort using percentiles Link and I didn't understand why when we do a 25-75 split the running time will be O(n log n)? I tried to develop the recursion tree and I didn't have any result.

Thank you

CodePudding user response：

Assuming larger partition is always 75%, then number of recursions is log1/.75 = log1.5. In best case, larger partition is always 50% and number of recursions is log1/.5 = log2. Since time complexity ignores constant factors, both cases are considered to be O(n log(n)).