Let $\lbrace x_i\rbrace_{i=1}^\infty$ be a sequence of distinct numbers in $(0,1)$. For any $n$ after deleting $x_1,...,x_n$ from $[0,1]$ we get $n+1$ subintervals. Let $a_n$ be the maximum length of these subintervals. Is there any sharp lower bound for $\limsup_n na_n$ ?

Here is how to achieve $1/\ln 2$. It is a modification of Harald's construction. We take the sequence $1/2$, $1/4$, $3/4$, etc. and apply the transformation $x \to \ln (1+x)/\ln 2$. So the sequence is $\ln(3/2)/\ln(2), \ln(5/4)/\ln (2),\ln(7/4)/\ln(2),\dots$ The general terms is $x_n$ for $n=2^a+b$ with $b<2^a$ is $$\ln \left( \frac{2^{a+1} + 2 b+1}{2^{a+1}}\right)$$ or, equivalently $$\frac{\ln( 2^{a+1}+2 b + 1)}{\ln(2)}  a1$$ Then after $n = 2^a + b$ steps for $b<2^a$, we will have just added the cut $(2 b+1 ) /(2^{a+1})$, the largest interval will be $$\left[\frac{\ln( 2^{a}+2 b + 1)}{\ln(2)}  a, \frac{\ln( 2^{a}+2 b + 2)}{\ln(2)}  a\right] $$ whose length is: $$\frac{ \ln \left(1 + \frac{1}{2^{a}+b+1}\right)}{\ln 2}$$ If we multiply by $2^a+b+1$, the $\lim\sup$ is $1/\ln 2$. To show this is optimal, form a binary tree where the vertices are intervals that appear at any point in a sequence. Each interval at some point splits into two intervals, which gives the tree structure. Label each vertex with the step at which it splits. For any $\beta>\lim\sup n a_n$, for all but finitely many vertices, the length of the interval labeled $n$ is at most $\beta/n$. The sum of the lengths of the intervals on each row is $1$, so the sum of the first $k$ rows is $k$. Thus $k$ is at most the sum over $2^k1$ distinct numbers $n$ of $\beta/n$ plus a constant coming from the finitely many vertices where the length is not at most $\beta/n$. So $k$ is at most the sum over the first $2^k1$ numbers of $\beta/n$ plus a constant, which is at most $\beta k \ln 2$ plus a constant. So $\beta\geq 1/\ln 2$. So $\lim\sup n a_n \geq 1/\ln 2$. 


Added: As John Bentin mentions it is in fact known that the result I mentioned below for the dispersion and thus the $1/\log 2$ of OP (mentioned in now deleted comments) is optimal. This appears originally in Niederreiter, On a measure of denseness for sequences. In: Topics in classical number theory, NorthHolland, Amsterdam, 1984. An easier accssible source is the book by Niederreiter 'Random Number Generation and Quasi Monte Carlo Methods' (SIAM, 1992). There it is Theorem 6.7. That there cannot be a better sequence is due to Niederreiter, but the example given there showing it is optimal is attributed to Ruzsa. The example there is $x_1 = 1$ and then $$x_n = \left \{ \frac{\log (2n3)}{ \log 2} \right \}.$$ The above mentioned book is available as a scan from Niederreiter's webspace (note is about 10Mb). In a comment I mentioned the keyword low discrepancy sequence, which indeed is related, but the better keyword and really what is asked for is a low dispersion sequence. The dispersion of a finite point $P=\{x_1, \dots , x_n\}$ set in some ambient space $S$ is defined as the supremum over all $x \in S$ of $\min_i d(x,x_i)$ where in the paper I quote the $d$ is the infinitynorm (but since be are in 1d it does not matter so much). And, then for a sequence one considers the dispersion of the intial segements. Thus the limes superior of $n$ times the dispersion of the first $n$ elements of the sequence is just half of what is asked here (actually, one one might have to be slightly careful to include 0 and 1 to be save and thus multiply by $n+2$, but asymptically this does not change anything). This notion of disperson, it appears, was introduce by Niederreiter and in his paper 'Lowdiscrepancy and lowdispersion sequences' (J. Number Th., 1987), see at the very end, he reports that the then best construction of a low dispersion sequence yields a $1/\log 4$ which indeed is just half of the $1/\log 2$ that OP reports. (The construction is not in this paper of Niederreiter but he quotes it; I should add that the result is for arbitrary dimesion the 1d case might or might not be older). There seems to be various related work so one might find more with more extended searches. 


Edit: here is a simple proof that $\alpha := \inf \limsup n a_n \geq 1/\ln 2$. Note that this edit is made after solutions have been given in other answers. Let us consider the sequence of lengths of the subintervals at some step $n$, in decreasing order: $\ell_0\geq\ell_1\geq\dots\geq\ell_n$ so that $\ell_0=a_n$. Assume that we look at one of the worst steps, so that $k a_k\leq n a_n$ for all $k>n$. Then $j$ step later, there is at least one subinterval of length $\ell_j$, since not all longest one can have been subdivided. That implies $$ \ell_j \leq \ell_0\frac{n}{n+j} = a_n\frac{1}{1+j/n}$$ Moreover, the sum of the $\ell_\ast$ must be $1$, so that $$1=\sum \ell_j \leq a_n\sum_j \frac{1}{1+j/n} \sim a_n \cdot n\int_0^1\frac{\mathrm{d}t}{1+t}= na_n \ln 2$$ This proves $\limsup n a_n \geq 1/\ln 2$. We also get a hint on how to realize it: at each step, divide the longest interval in a way that makes the distribution of length closest to the profile $t\mapsto \frac1{1+t}$ over $[0,1]$. This is not a complete answer, but nonmatching upper and lower bound for $\alpha := \inf \limsup n a_n$ (where the infimum is on $\{x_n\}$ and the supremum limit on $n$): $$\frac12+\frac1{\sqrt{2}} \simeq 1,207 \leq \alpha \leq \frac{1+\sqrt{5}}2 \simeq 1,618$$ For the lower bound: let $\{x_n\}$ be fixed and assume that for big enough $n$, all pieces have length at most $a/n$ (where $a\geq1$). Let $\psi$ be a number less than $1$ to be optimized later on, let me ignore roundoff errors that are negligible, and look at the $n\psi$th largest piece at step $n$. Denote its length by $\ell$: the total length of the pieces is $1$ and is also at most $a/n\cdot n\psi+\ell n(1\psi)$, so that $$\ell \geq \frac{1a\psi}{1\psi}\cdot\frac1n.$$ Since there are at least $\psi n$ pieces of size at least $\ell$, at a step of the order of $n+\psi n$ there will be one such piece remaining. Therefore we have $$\frac a{n+\psi n} \geq \frac{1a\psi}{1\psi}\cdot\frac1n$$ from which it comes $$a\geq \frac{1+\psi}{1+\psi^2}.$$ Optimizing in $\psi$ gives the desired lower bound. For the upper bound: we seek a way to achieve $\limsup n a_n=\phi$ where $\phi=\frac{1+\sqrt{5}}2$ is the golden ratio. Fix $\lambda \leq 1/2$, and construct $\{x_n\}$ inductively so as to cut at each step the largest interval in two parts of lengths in the ratio $\lambda:1\lambda$. To simplify the analysis, then choose $\lambda$ so that $(1\lambda)^2=\lambda$ (i.e. take $\lambda=\frac{3\sqrt{5}}2$). With this choice, we get that at each step $n$ all pieces are of lengths $\lambda^k$ or $\lambda^{k1}(1\lambda)$, for some $k$ that depends only on $n$. Rather than express $k$ in function of $n$, let us consider the worse case: there are $n$ pieces of length $\lambda^k$ and only one of length $\lambda^{k1}(1\lambda)$. Then as the sum of the lengths is $1$, writing $\ell=\lambda^k$ and noticing $\phi=\frac{1\lambda}{\lambda}$, we can compute $\ell=\frac{1}{n+\phi}$ so that (for those $n$ when we are in the worstcase scenario): $$n a_n = \frac{n\phi}{n+\phi}\to\phi.$$ 

