I need to show that, for any running time $T(n)$ that is both $\Omega(n\log n)$ and $O(n^2)$ it is possible to give QuickSort some sequence of inputs such that the running time will grow as $\Theta(T(n))$.
I proved using the Master Method that an already sorted input of length $n$ will require $n\log n$ time. I proved by substitution that an array containing repetitions of a single number will run in $n^2$ time.
Now I'm thinking that if I want any possible run time then I should try to set it up in the third case of the Master Method where the run time is determined by $f$ in
$$S(n)=aS(n/b)+f(n)$$
So that I try making $T(n)=f(n)$ here. However, a few things seem like obstacles here. First, I don't think I can always get the problem to reduce to a fraction of its previous size, since the limit case employs $S(n)=S(n-1)+n$. Second, the Master Method doesn't accommodate all possible run times, but only run times satisfying certain conditions. So I might be going down the wrong path here.
However, if I try to take it from the start, the problem seems way too general to tackle directly. I wouldn't know where to start. I can sort of suspect that the answer might be some mixture of my two solutions above, maybe a list that has a first portion all repetitions of a certain number, and then incrementing by 1 starting at some particular index. But I couldn't see how to determine that index to get a general growth function $T(n)$.