This recurrence relation
$$ T(n) = T(n - \log(n))+cn $$ is one I came up with from a computer science problem I was studying, but I'm not sure what a closed form or precise time complexity would be. This isn't a homework problem or anything and I'm not looking for hints to keep working on it, I'm just curious if anyone could provide a solution or answer with an argument. Thank you.
EDIT: As a commenter has kindly pointed out, it would make more sense if floor or ceiling was used, so I'll adjust it to
$$ T(n) = T(n - \lfloor\log(n)\rfloor)+cn $$
The original scenario for context: Consider quick sort where the average element (or element closest to the average) is always selected (assume that this pivot can be found in $O(1)$ time).
I've been wondering what the time complexity would be if the input was a list of exponentially growing numbers, e.g. $[2, 4, 8, 16, ..., 2^n]$. I've determined that the pivot would split the largest subarray in one level of recursion into two subarrays of size roughly $n-\log(n)$ and $\log(n)$. And hence I came to the described recurrence relation.
EDIT 2: Well, I suppose more accurately there would also be a $T(\lfloor \log(n)\rfloor)$ in the recurrence. I don't know how much difference it makes. I guess equivalently for this question, what I'm wondering is what the recursion height would be for this example scenario.
I'll use the recurrence with the extra term, although I don't think it makes a difference, it just makes the proof slightly more complicated.
$$ T(n)=T(n-\lfloor \log(n)\rfloor)+T(\lfloor \log(n)\rfloor)+cn $$
Now, let $f(x)=\int_{10}^x t/\lfloor \log(t)\rfloor dt$. (The integral starts from $10$ to avoid $\lfloor\log(t)\rfloor=0$.) Then, I believe that $T(n)=\Theta(f(x))$.
We need to prove there exist constants $c_1, c_2$ such that for all sufficiently large $n$, $$ c_1 f(n) \leq T(n) \leq c_2 f(n) $$ We prove the inequalities by induction, the base case is trivial. For the recurrence case, first let's prove $T(n)\leq c_2 f(n)$. By the recurrence, we have: $$ T(n) \leq c_2 f(n-\lfloor \log(n)\rfloor) + c_2f(\lfloor \log(n)\rfloor) + cn $$ By Taylor's theorem, there exists $n-\lfloor \log(n)\rfloor < n^* < n$ such that: $$ f(n-\lfloor \log(n)\rfloor)=f(n)-f'(n^*)\lfloor \log(n)\rfloor=f(n)-\frac{n^*}{\lfloor\log(n^*)\rfloor}\lfloor \log(n)\rfloor $$ Substitute into the inequality: $$ T(n)\leq c_2f(n)-c_2\frac{n^*}{\lfloor\log(n^*)\rfloor}\lfloor \log(n)\rfloor + c_2f(\lfloor \log(n)\rfloor) + cn $$ Since $n^* < n$ and $x/\lfloor \log(x)\rfloor$ is an increasing function, we can replace $n^*/\lfloor\log(n^*)\rfloor$ with $n/\lfloor\log(n)\rfloor$ and simplify the inequality: $$ T(n)\leq c_2f(n)-c_2n + c_2f(\lfloor \log(n)\rfloor) + cn $$ Now, notice that $f(x)=\int_{10}^x t/\lfloor \log(t)\rfloor dt\leq \int_{10}^x tdt=x^2/2-10^2/2 \leq x^2$. Thus, $f(\lfloor \log(n)\rfloor)\leq \log^2(n)$, so $f(\lfloor \log(n)\rfloor)$ is $o(n)$. I am using little-o here, which means for any constant $C$ and sufficiently large $n$, $f(\lfloor \log(n)\rfloor)\leq Cn$. For convenience, I will choose $C=1/3$: $$ T(n)\leq c_2f(n)-c_2n + c_2\cdot \frac{1}{3}n + cn=c_2f(n)-\left(\frac{2}{3}c_2-c\right)n $$ Now, we can choose any constant $c_2$ we want, as long as $c_2$ is a constant which is independent of $n$, so let's choose $c_2=3c$. Then, $(2/3)c_2-c=c$, so we get: $$ T(n) \leq c_2f(n)-cn\leq c_2f(n) $$ as was to be proven.
Using a similar strategy with Taylor's theorem, I believe you can also prove $c_1 f(n)\leq T(n)$ and once you prove that, that would suffice to show $T(n)=\Theta(f(n))$.