How to solve the recurrence $T(n) = T(\lfloor \log(n) \rfloor) + \lfloor\log(n)\rfloor + 1$ , for $n \geq1$

58 Views Asked by At

I need to find the closed form for the recurrence
$T(n) = T(\lfloor \log(n) \rfloor) + \lfloor\log(n)\rfloor + 1$

When trying to solve it, I end up with this series
$\lfloor \log(n) \rfloor + \lfloor\log(\lfloor \log(n) \rfloor)\rfloor + \lfloor\log(\lfloor\log(\lfloor \log(n) \rfloor)\rfloor)\rfloor + .... + 1$
and I cant solve it further.

where $n\geq 1$.
For more background context, I need to find the number of bits used to encode a natural number N, using elias-omega encoding, which, if I am correct, should be given by this formula.