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

Question

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 dividng the array around
a particular pivot point so while calcualting the time complexity of quick-sort why do we take O(n)
time for f(n) ,how is acting as a conquering step?

Answer 1

Here , conquering cost is  O(1)

and partition algo { O(n) } is the cost for dividing the big problem into small sub-problems.

So,    T(n) =       O(n)            +              T(k * n )  +   T( (1-k)* n )            +             O(1)

                     Divide cost                 Sub-problems' cost                  Combine-Cost

---

Note: f(n) as u described is Divide + Conquer cost  , not just conquer. 

Answer 2

Actually at each step we are combining n elements.