Recurrence T(N)=T(N/LOGN)+1 [closed]

Question

I'm stuck on the following reccurrence :

T(N)=T(N/LOGN)+1,IF N>2
T(N)=0,if 0<=N<=2

I need a function T(N) for all N>0 Is there some method for solving it? Can we at least get some tight asymptotic bounds for T(N)?

UPD1: LOG is binary logarithm, log with base 2.

Answer 1

$$T(n) = \frac{\log_2 n}{\log_2\log_2 n}$$ is a near-solution of the difference equation for large $n$. I expect this is the correct rate of growth and probably one can prove that by bounding the error term.

In fact there seems to be an asymptotic solution that starts $$T(n) = \frac{\log_2 n }{\log_2\log_2 n }\left(1 + \frac{1}{\log\log_2 n} + \frac{2}{(\log\log_2 n )^2} + \cdots \right),$$ where I left off the subscript on the log a few times on purpose.

So let's finish the proof. For constants $c,C$, define $$T_{c,C}(n) = \frac{\log_2 n }{\log_2\log_2 n }\left(1 + \frac{c}{\log\log_2 n}\right) + C.$$ By direct calculation, there is an $n_0$ such that for $n\ge n_0$ $$T_{c,C}(n)-T_{c,C}(n/\log_2 n) ~~\begin{cases} {}\lt 1 \text{ if $c=0$}\\\\ {}\gt 1 \text{ if $c=1$.}\end{cases} $$ (Note that $n_0$ is independent of $C$.) The recurrence for $T(n)$ starting at $n\gt n_0$ always lands in the interval $I=[n_0/\log_2 n_0,n_0]$. Choose constants $C_0,C_1$ such that $$T_{0,C_0}(n) \lt T(n) \lt T_{1,C_1}(n)$$ for $n\in I$, then induction shows it to be true for $n\gt n_0$ too.

In summary, we have proved that as $n\to\infty$, $$T(n) = \frac{\log_2 n }{\log_2\log_2 n }\left(1 + \frac{O(1)}{\log\log_2 n}\right).$$

Answer 2

I'm not sure the approximation above $(LOG_2n)*(LOG_2LOG_2n)$ is correct.

Let's formulate the task in the folllowing way:

We have some number N>2,and we can divide it  by $LOG_2 (N)$ while we get a number that is smaller or equal to 2. How many iterations do we need?

For $N>4$ $LOG_2(N)>2$,so,if we have sufficiently large N-- let's divide it by log(N) each time while we get a number which is <= 4. The number of iterations we will apply before we get a number that is smaller than 4 is < $LOG_2(N)$(because we divide by a number which is larger than 2 each time),while for N<4 the number of iterations is constant (Actually it is 1 ) and and we can ignore it for sufficiently large N.

It means we have O(LogN) as an upper bound.

So,the exercise from the book is solved. But, just out of curiosity, I'm interested more in some method to solve the equation and to get the exact solution. I'm not sure we can replace the difference equation with the differential equation here.

Answer 3

A computation: the Mathematica 8 commands:

 F[A_]:=F[A]=-((A ProductLog[-1,-(Log[2]/A)])/Log[2]);
 N[NestList[F, 2, 15]]

gives the following breakpoints for $T$:

$2.,4.,16.,108.099,1090.86,15148.6,273611.,6.17193\times 10^6,$

$1.68677\times 10^8,5.45588\times 10^9,2.05015\times 10^{11},8.81634\times 10^{12},$

$4.2853\times 10^{14}, 2.32997\times 10^{16},1.40462\times 10^{18},$

$9.31777\times 10^{19}$

That is, $T(n)=1$ for $2 < n \leq 4$, $T(n)=2$ for $4 < n \leq 16$, $T(n)=3$ for $16 < n < 108.09$, and so on.

This suggests that $\log_2 n \log_2\log_2 n$ is significantly too fast. Perhaps the square root of this is closer to the truth.

Answer 4

Given an initial value of $n = 2^i$, the argument is gradually reduced so that after one stage it is $2^{i - \log i}$, and so forth. If we examine the exponent alone, it satisfies $$ i(0) = \log_ n, i(k+1) = i(k) - \log i(k) $$

We approximate this difference equation with the differential equation $$ y(0) = \log_2 n, y'(x) = -\log_2 y(x) $$ yielding $$ -\ln 2 li(y) = x - \ln 2 li(\log_2 n) $$ where $li$ is the logarithmic integral.

Up to a constant offset, the value $T(n)$ is the value of $x$ such that $y = O(1)$, that is, $$ T(n) = O(1) + \ln 2 li(\log_2 n) $$

For $n$ sufficiently large we have $li(x) \sim x/\ln x$. Hence we should have $$ T(n) \sim \frac{\log_2 n}{\log_2 \log_2 n} $$