2

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.

e13
  • 23
  • 4
  • 3
    Problem is, it's not a recurrence relation. The expression $n - \log(n)$ is rarely, if ever, an integer (depending on the base), so this relation will not make sense for a sequence $T(n)$. You may want to consider putting floor or ceiling functions somewhere in the expression $n - \log(n)$ to round it to an integer. Either that, or pivot from recurrence relations to functional equations, and find $T$ as a function of a real variable $n$. – Theo Bendit Mar 20 '24 at 04:23
  • Oh sorry, you're right. I didn't think about it when translating it from the original problem I was studying. I'll make an edit. Thanks. – e13 Mar 20 '24 at 04:47

1 Answers1

1

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))$.

Noble Mushtak
  • 18,402
  • 28
  • 44
  • Thank you very much, I really appreciate it. Can I ask how you came up with f(x)? Is it intuition from having seen other recurrences in the past? – e13 Mar 20 '24 at 21:17
  • Also, a side question, do you know if it's correct or wrong to claim that $\frac{x^2}{\ln(x)} = \Theta(f(x))$ (I'm using real variables for simplicity)? I see that $\frac{d}{dx}(\frac{x^2}{\ln(x)}) = \frac{2x}{\ln(x)} - \frac{x}{(\ln(x))^2}$. I'm not sure how impactful the $\frac{x}{(\ln(x))^2}$ in the derivative is, asymptotically. – e13 Mar 20 '24 at 21:46
  • 1
    My intuition was based on this post: https://math.stackexchange.com/questions/3195721/solve-the-recurrence-relation-tn-tn-sqrt-mathstrut-n-t-sqrt-mat?rq=1 where they had a similar recurrence with $n-\sqrt{n}$ instead of $n-\log(n)$, and the answer was a multiple of $(2/3)n^{3/2}$, which is the antiderivative of $\frac{n}{\sqrt{n}}$. – Noble Mushtak Mar 21 '24 at 00:27
  • 1
    Also I didn't think of that but looking at it now, yes $x^2/\log(x)$ also works. Basically, that extra $x/\log^2(x)$ term in the derivative would become $x/\log(x)$ in the right-hand side of the inequality (because we're multiplying the derivative by $\log(x)$), and then using the fact that $x/\log(x)=o(x)$, where the "o" here is little-o, you can basically show that the $x/\log(x)$ term doesn't matter and doesn't affect the complexity analysis. – Noble Mushtak Mar 21 '24 at 00:27