I would have guessed that $T(n)$ is in $\Theta(n \log n)$, so below is an attempt to lower bound the recurrence. Corrections (major as well as minor) and comments are very welcome.

For simplicity, I assume $ n = 20k + 1 $, as in fade2black's answer, with $ k = \frac{n-1}{20} $.

Thus,

$$ T(n) \geq \sum^{k-1}_{i=0}\log(n-20i) \geq \sum^{k/2}_{i=0}\log(n-20i) = $$

$$ \log(n) + \log(n - 20) + \log(n - 40) + ... + \log(n - 20(k/2)) $$

But,

$$ n - 20(k/2) = n - 20(\frac{n-1}{20})/2 = n - \frac{n-1}{2} \geq n/2 $$

Hence,

$$ \sum^{k/2}_{i=0}\log(n-20i) \geq \frac{k}{2} \times \log(n/2) \geq \frac{n-1}{40} \times \log(n/2) \in \Theta(n \log n) $$

So, it seems like the $ n \log n $ bound is tight after all.

I would have guessed that $T(n)$ is in $\Theta(n \log n)$, so below is an attempt to lower bound the recurrence. Corrections (major as well as minor) and comments are very welcome.

For simplicity, I assume $ n = 20k + 1 $, as in fade2black's answer, with $ k = \frac{n-1}{20} $.

Thus,

$$ T(n) \geq \sum^{k-1}_{i=0}\log(n-20i) \geq \sum^{k/2}_{i=0}\log(n-20i) = $$

$$ \log(n) + \log(n - 20) + \log(n - 40) + ... + \log(n - 20(k/2)) $$

But,

$$ n - 20(k/2) = n - 20(\frac{n-1}{20})/2 = n - \frac{n-1}{2} \geq n/2 $$

Hence,

$$ \sum^{k/2}_{i=0}\log(n-20i) \geq \frac{k}{2} \times \log(n/2) \geq \frac{n-1}{40} \times \log(n/2) \in \Omega(n \log n) $$

So, it seems like the $ n \log n $ bound is tight after all.

I would have guessed that $T(n)$ is in $\Theta(n \log n)$. So, below is a sketchy "proof" of that. Please take it with caution since I mostly do systems and not theory/analysis work (so far?). Corrections (major as well as minor) and comments are very welcome.

For simplicity, I assume $ n = 20k + 1 $, as in fade2black's answer, with $ k = \frac{n-1}{20} $.

Thus,

$$ T(n) \geq \sum^{k-1}_{i=0}\log(n-20i) \geq \sum^{k/2}_{i=0}\log(n-20i) = $$

$$ \log(n) + \log(n - 20) + \log(n - 40) + ... + \log(n - 20(k/2)) $$

But,

$$ n - 20(k/2) = n - 20(\frac{n-1}{20})/2 = n - \frac{n-1}{2} \geq n/2 $$

Hence,

$$ \sum^{k/2}_{i=0}\log(n-20i) \geq \frac{k}{2} \times \log(n/2) \geq \frac{n-1}{40} \times \log(n/2) \in \Theta(n \log n) $$

So, it seems like the $ n \log n $ bound is tight after all.

I would have guessed that $T(n)$ is in $\Theta(n \log n)$, so below is an attempt to lower bound the recurrence. Corrections (major as well as minor) and comments are very welcome.

For simplicity, I assume $ n = 20k + 1 $, as in fade2black's answer, with $ k = \frac{n-1}{20} $.

Thus,

$$ T(n) \geq \sum^{k-1}_{i=0}\log(n-20i) \geq \sum^{k/2}_{i=0}\log(n-20i) = $$

$$ \log(n) + \log(n - 20) + \log(n - 40) + ... + \log(n - 20(k/2)) $$

But,

$$ n - 20(k/2) = n - 20(\frac{n-1}{20})/2 = n - \frac{n-1}{2} \geq n/2 $$

Hence,

$$ \sum^{k/2}_{i=0}\log(n-20i) \geq \frac{k}{2} \times \log(n/2) \geq \frac{n-1}{40} \times \log(n/2) \in \Theta(n \log n) $$

So, it seems like the $ n \log n $ bound is tight after all.