The question is clear in the title. I am trying to solve this recursion as a part of showing that the worst case of quicksort algorithm occurs when $k=0$, but can’t do it. I could do the following specific cases (by repeatedly using the same recursion):

1)$T(n)=T(n-1)+O(n)$

2)$T(n)=2T(frac n2)+O(n)$

Can anybody please help me to solve this general case?

**P.S.** I don’t know Master’s theorem, so I would appreciate a solution without using that (In case that is applicable here).