2
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ In my solution I didn't provide lower bound. Are you searching for upper bound or tight bound? $\endgroup$
    – fade2black
    Jul 29, 2017 at 10:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – M.Mac
    Jul 29, 2017 at 11:02
  • 1
    $\begingroup$ I doubt that $n\log{n}$ is the lower bound for this recursive relation. $\endgroup$
    – fade2black
    Jul 29, 2017 at 11:05
  • $\begingroup$ i am sorry that i cannot provide much information, but my solution paper says "$T(n) = \Theta(nlog(n))$". $\endgroup$
    – M.Mac
    Jul 29, 2017 at 11:10
  • $\begingroup$ 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. $\endgroup$
    – M.Mac
    Jul 29, 2017 at 11:17

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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})$ . $\endgroup$
    – fade2black
    Jul 29, 2017 at 17:03
  • 1
    $\begingroup$ @fade2black You're right. I was showing the tightness as a follow-up on your upper bound though. Thanks for the edit! $\endgroup$
    – Omar
    Jul 29, 2017 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.