Solve the recurrence relation $B(n) = 3B(n/log_2(n))+\theta(n)$

Question

What is the solution of following recurrence relation.

$B(2) = 1$

$B(n) = 3B(n/\log_2(n))+\Theta(n)$​

Answer 1

put n=2^k eq-1

B(2^k) = 3B(2^k/k) + 2^k

B(2^k/k) = 3B(2^k/k^2) + (2^k)/k

B(2^k/k^2) = 3B(2^k/k^3) + (2^k)/k^2

................=3B(2^k/k^x) + (2^k)/k^(x-1)

put 2^k/k^x=2...........eq-2

               = 3B(2) + (2^k)/k^(x-1)+...........+  (2^k)/k^2 + (2^k)/k  + 2^k

               =3*1+(2^k)[1/k^0 + 1/k^1  +  1/k^2+  1/k^3  +1/k^4 +1 /k^(x-1)]    apply g.p formula=a(1-r^n)/1-r

                =3+(2^k)[(1-(1/k)^x)/1-1/k]

                =3+(2^k) *k*[(k^x-1)]/(k-1) k^x

           put k^x=2*2^k  from eq-2

                  =(k.2^K)/(k-1)

put 2^k=n from eq-1

             =n.logn  is the answer

Comments

+1 for thinking of substituting $n=2^k$. But I think that B(n) $\in$ a much tighter bound.