Trying to find a substitution to solve a recurrence

Question

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*}

Answer 1

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

Answer 2

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.