# Solving a T(n) recursion without Master Theorem

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

• In my solution I didn't provide lower bound. Are you searching for upper bound or tight bound? – fade2black Jul 29 '17 at 10:55
• First of all thanks you. In my task i was only searching for the asymptotic runtime in $\Theta$ notation, but $\mathcal{O}$ should be fine. – M.Mac Jul 29 '17 at 11:02
• I doubt that $n\log{n}$ is the lower bound for this recursive relation. – fade2black Jul 29 '17 at 11:05
• i am sorry that i cannot provide much information, but my solution paper says "$T(n) = \Theta(nlog(n))$". – M.Mac Jul 29 '17 at 11:10
• Maybe they say its theta, because it starts with T(1)=1 which means we are in the range $0<c< \infty$. With c as result of the equation. – M.Mac Jul 29 '17 at 11:17

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.

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.

• You demonstrate the lower bound so it would be right to finish as $\in \Omega(n\log{n})$ instead of $\in \Theta(n\log{n})$ . – fade2black Jul 29 '17 at 17:03
• @fade2black You're right. I was showing the tightness as a follow-up on your upper bound though. Thanks for the edit! – Omar Jul 29 '17 at 17:37