Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

closed as too localized by Will Jagy, Felipe Voloch, Chandan Singh Dalawat, Andy Putman, Suvrit Mar 11 '12 at 23:03

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
Well, there is no such function. Check N = e, for example. –  Woett Mar 10 '12 at 22:11
    
Oh sorry,the log is "binary" log with base 2. –  iensen Mar 10 '12 at 22:14
    
T(n) will be bounded above by log(n) with the log base being 2. It is likely to be approximated for large n by something like log(n/log(n)), but I have not verified this. Gerhard "Ask Me About System Design" Paseman, 2012.03.10 –  Gerhard Paseman Mar 10 '12 at 22:18
    
This looks vaguely (but probably not exactly) like questions asked on math.stackexchange.com - where does this recurrence relation originate? –  Yemon Choi Mar 10 '12 at 22:24
1  
This equation (like most questions on math.stackexchange.com,but i didn't find exactly this one) originate from Cormen's book about algorithms. It is not stated clearly anywhere but it can be composed on the base of one of the book's chapters. –  iensen Mar 10 '12 at 22:29

4 Answers 4

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
I don't verify your de solution. I get that $y(x)=log_2(n)−(log 2) li(x)$ satisfies $y'(x)=-1/log_2(x)$. –  Brendan McKay Mar 11 '12 at 13:41
    
Computations, however, show that $T(n)/(\log_2 n \log_2\log_2 n)$ goes steadily to 0. –  Kevin O'Bryant Mar 11 '12 at 13:54
    
The edit improves things, but still calculations show a slow but monotonic decrease in $T(n)/( \log_2 n /\log_2\log_2 n )$ evaluated at the $n$ where $T$ jumps up (at least, in the range $4<T<20$), and definitely dropping below 1. Disclaimer: small numbers, and all that. –  Kevin O'Bryant Mar 11 '12 at 14:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.