Solving a T(n) recursion without Master Theorem

Question

i have a problem solving the recursion $T(n) = T(n-20)+log(n)$, because the Master Theorem is not applicable in this case.

This is my attempt:
$T(1) = 1$(given)
$T(n) = T(n-20)+log(n)$
$T(n) = T(n-20-20)+log(n-20)+log(n) $
...
...
$T(n) = T(n-k)+log(n-(k-20))+....+log(n)$

Let be $ k = n-1$
$T(n) = T(n-(n-1)) +log(n-(n-1-20)+...+log(n)$
$T(n) = T(1)+log(21)+....+log(n)$

Which results in:
$ 1+ \sum_{n=1}^{\frac{n}{20}} ???$(i dont know if this is correct)

I am searching for a final result, which should be $\Theta(nlog(n))$

Answer 1

Start with $$T(1)= 1$$ $$T(21)= T(1)+\log(21)$$ $$T(41)= T(21)+\log(41)$$ $$\dots$$ $$T(20k+1)= T(19k+1)+\log(20k+1)$$ Then move $T(i)$s from the right side to the left side $$T(1)= 1$$ $$T(21) - T(1) = \log(21)$$ $$T(41) - T(21) = \log(41)$$ $$\dots$$ $$T(19k+1) - T(18k+1) = \log(19k+1)$$ $$T(20k+1) - T(19k+1) = \log(20k+1)$$ And sum the left and right sides

$$T(20k+1) = 1 + \log(21) + \dots + \log(20k+1) \leq 1 + \sum_{i=1}^{k}{\log(21i)} = $$ $$1 + \sum_{i=1}^{k}{[\log(21)+\log(i)]} \leq 1+ \sum_{i=1}^{k}{\log(21)}+ \sum_{i=1}^{k}{\log(k)} = $$ $$1 + k\log(21) + k\log(k)$$ which is $O(n\log{n})$. This was only upper bound.

More general case

There is nothing special with the integers 1 and 20. You could take any positive integers instead of 1 and 20 and solve the relation

$$T(b) = c$$ $$T(n)= T(n-s) + \log{n}$$ as $$T(b) = c$$ $$T(s+b) = T(b) + \log{(s+b)}$$ $$T(2s+b) = T(s+b) + \log{(2s+b)}$$ $$\dots$$ $$T((n-1)s+b) = T((n-2)s+b) + \log{((n-1)s+b)}$$ $$T(ns+b) = T((n-1)s+b) + \log{(ns+b)}$$ which gives $$T(ns+b) = c + \log{(s+b)}+\log{(2s+b)}+\dots + \log{(ns+b)}$$

Is $n\log{n}$ a lower bound for this relation?

UPDATE: Omar's post attempts to establish a lower bound.

Answer 2

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.