Trying to find a substitution to solve a recurrence I'm trying to solve the  following recurrence.

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

Here is my attempt:

\begin{align*}
B(n)
&amp;= 3B(\lceil n/\log_2 n\rceil) + \Theta(n)\\
&amp;= 3\big(3B(\lceil n/(\log_2 n)^2\rceil) + \Theta(n)\big) + \Theta(n)\\
&amp;= 3\big(3\big(3B(\lceil n/(\log_2 n)^3\rceil)\big)\big) + 3^2\Theta(n) + 3\Theta(n) + \Theta(n)\\
&amp;\ \ \vdots\\
&amp;= 3^{k-1}B(\lceil n/(\log_2n)^{k-1}\rceil) + (1 + 3 + \dots + 3^{k-1})\Theta(n)\\
&amp;= 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)
&amp;= 3B(\lceil n/\log_2 n\rceil) + \Theta(n)\\
&amp;= 3\big(3B(\lceil (n/(\log_2 n))/(\log_2(n/(\log_2 n) \rceil) + \Theta(n)\big) + \Theta(n)\\
&amp;\ \ \vdots\\
\\
,.
\end{align*}
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) &amp;= \Theta\left(n + \frac{n}{\log n} + \frac{n}{\log n \log(n/\log n)} + \cdots\right) \\ &amp;=
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)$.