I am reading the book Analysis of Algorithms. The focus of chapter 1 is to analyze the running time of the original Quicksort algorithm. The code of this algorithm is given in the book.

`public class Quick { private static int partition(Comparable[] a, int lo, int hi) { int i = lo, j = hi+1; while (true) { while (less(a[++i], a[lo])) if (i == hi) break; while (less(a[lo], a[--j])) if (j == lo) break; if (i >= j) break; exch(a, i, j); } exch(a, lo, j); return j; } private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) return; int j = partition(a, lo, hi); sort(a, lo, j-1); sort(a, j+1, hi); } } `

There is an exercise at the end of chapter 1 asking the number of subarrays with size `k`

or less.

`How many subarrays of size k or less (not counting subarrays of size 0 or less) are encountered, on the average, when sorting a random file of size N with quicksort? `

For simplicity, I will only count the subarrays with the size exactly `k`

. My approach to this problem is building a recurrence equation. Let $ C(n)$ be the average number of subarrays with the size `k`

encountered during quicksort. We have $ C(n) = \frac{2}{n}\sum_{i=1}^{N-1}C(i)$ . Simplify this equation using the same technique in the book, we have $ C(n)=\frac{n+1}{n}C(n-1)$ . Because $ C(n)=0$ with $ n<k$ and $ C(n)=1$ with $ n=k$ . So by expanding the equation and canceling the factor, we have $ C(n)=\frac{n+1}{k+1}$ . So the answer of the original problem is $ (n+1)(\frac{1}{2}+…+\frac{1}{k+1})$ .

Is this a correct way to solve this problem? Did I miss something in my arguments above?