Search code examples
algorithmtime-complexitytheory

How does partitioning step acts as a conquering step in quick sort?


Time complexity for recurrence relations is given by : T(n) = aT(n/b) + f(n) here f(n) is the cost of conquering the sub-problems i.e. cost of merging all the sub-problems in order to solve the problem but in case of partioning we are dividing the array around a particular pivot point so while calculating the time complexity of quick-sort why do we take O(n) time for f(n).

How is this acting as a conquering step?


Solution

  • Don't understand what you mean by conquering step.

    f(n) is in fact the cost of anything done in your recursive function, that happens well before, after, or between your recursions.

    In the case of quick sort, the cost of merging the solutions of the partitions is 0, as you don't need to do anything after the left and right sides of the pivot are sorted. The whole cost is in producing the partitions, and to do that, you need to position your selected pivot. This is why quick sort is classified as a Hard Split Easy Join kind of Divide and Conquer.

    The cost of positioning the pivot is O(n), as you have to move from left to right and from right to left, finding items in the wrong side of the pivot, and swapping them, until both searches (from left to right and from right to left) cross each other.

    Hope this helped in your understanding, and sorry if I misunderstood completely your question.