2
$\begingroup$

I'm trying to solve the following recurrence.

\begin{align*} B(2) &= 1\\ B(n) &= B(\lceil n / \log_2 n\rceil)+\Theta(n) \end{align*}

Here is my attempt:

\begin{align*} B(n) &= 3B(\lceil n/\log_2 n\rceil) + \Theta(n)\\ &= 3\big(3B(\lceil n/(\log_2 n)^2\rceil) + \Theta(n)\big) + \Theta(n)\\ &= 3\big(3\big(3B(\lceil n/(\log_2 n)^3\rceil)\big)\big) + 3^2\Theta(n) + 3\Theta(n) + \Theta(n)\\ &\ \ \vdots\\ &= 3^{k-1}B(\lceil n/(\log_2n)^{k-1}\rceil) + (1 + 3 + \dots + 3^{k-1})\Theta(n)\\ &= 3^{k-1} B(\lceil n/(\log_2 n)^{k-1}\rceil) + \frac{3^k-1}{3-1}\Theta(n)\,. \end{align*} Is there a substitution that I can use to make the term inside the function become 2?

Or any other smart method I can use to solve this problem?

I realised I made a mistake the expansion should be

\begin{align*} B(n) &= 3B(\lceil n/\log_2 n\rceil) + \Theta(n)\\ &= 3\big(3B(\lceil (n/(\log_2 n))/(\log_2(n/(\log_2 n) \rceil) + \Theta(n)\big) + \Theta(n)\\ &\ \ \vdots\\ \\ ,. \end{align*}

$\endgroup$
1
$\begingroup$

You don't need to try that hard. Instead, you can notice that on the one hand clearly $B(n) = \Omega(n)$, and on the other hand $$ \begin{align*} B(n) &= \Theta\left(n + \frac{n}{\log n} + \frac{n}{\log n \log(n/\log n)} + \cdots\right) \\ &= O\left(n + \frac{n}{2} + \frac{n}{4} + \cdots\right) = O(n). \end{align*} $$ The first inequality holds since for $n$ larger than some constant, $\log_2 n \geq 2$ (you just need to stop the recursion once $n$ gets too small, at the cost of additional $O(1)$ which gets swallowed in the big Theta). The second inequality holds since $n+n/2+n/4+\cdots = 2n$.

Formally speaking, you can argue that $B(n) = B(n/2) + \Theta(n)$ grows faster than $B(n) = B(n/\log_2 n) + \Theta(n)$.

$\endgroup$
  • $\begingroup$ Is there any way that I can find the tight bound? $\endgroup$ – dave Mar 9 '16 at 21:53
  • $\begingroup$ The tight bound is $\Theta(n)$, which is what I show in the answer. In case you also want to know the constant, then if $B(n) = B(n/\log_2 n) + Cn$, then $B(n) = Cn + o(n)$. $\endgroup$ – Yuval Filmus Mar 9 '16 at 21:57
  • $\begingroup$ I would not even mention the hand-wavy middle part. You found (or hinted at) quite elegant proofs fpr $B \in \Omega(n)$ and $B \in O(n)$ that start by finding upper/lower bounding recurrences that are easier to solve; no need to bother with the original. $\endgroup$ – Raphael Apr 9 '16 at 9:44
1
$\begingroup$

Expanding more and more $\Theta(n)$ is wrong.

Start by making the recurrence explicit; replace $\Theta(n)$ by $cn$. If your solution is $f(n)$ then, you know that $B \in \Theta(f)$ assuming everything behaves nicely.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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