Asymptotic value of a sequence Assume a real sequence $1=a_1\leq a_2\le \cdots \leq a_n$, and $a_{i+1}-a_i\leq \sqrt{a_i}$. Does this hold:
$$\sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} \in O(\log n)$$
 A: 
Lemma 1: If $1 = a_1 \leq a_2 \leq a_3 \leq \cdots$ and $a_{i+1}-a_i \leq \sqrt{a_i}$ then
  $$
\sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} = \Theta(\log a_n)
$$
  for all $n$.

Proof: By the assumptions we have
$$
0 \leq \frac{a_{i+1}-a_i}{a_i} \leq \frac{1}{\sqrt{a_i}} \leq 1,
$$
and since
$$
\frac{a_{i+1} - a_i}{a_i} = \frac{a_{i+1}}{a_i} - 1
\tag{1}
$$
this is equivalent to
$$
1 \leq \frac{a_{i+1}}{a_i} \leq 2.
\tag{2}
$$
If $1 \leq x \leq 2$ then
$$
\log x \leq x-1 \leq \frac{\log x}{\log 2},
$$
so setting $x = a_{i+1}/a_i$ in equations $(1)$ and $(2)$ yields
$$
\log \frac{a_{i+1}}{a_i} \leq \frac{a_{i+1} - a_i}{a_i} \leq \frac{1}{\log 2} \log \frac{a_{i+1}}{a_i}.
$$
Summing this over the range $i=1,2,\ldots,n-1$ yields
$$
\log \frac{a_n}{a_1} \leq \sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} \leq \frac{1}{\log 2} \log \frac{a_n}{a_1}.
$$
$$
\tag*{$\square$}
$$

Lemma 2: If $a_i \geq 1$ and $a_{i+1}-a_i \leq \sqrt{a_i}$ then $1 \leq a_i \leq i^2+2$.

Proof: Summing $a_{i+1}-a_i \leq \sqrt{a_i}$ over the range $i=1,2,\ldots,n-1$ yields
$$
a_i - 1 = \sum_{j=1}^{i-1} (a_{j+1} - a_j) \leq \sum_{j=1}^{i-1} \sqrt{a_i} \leq i\sqrt{a_i}
$$
and hence
$$
a_i - i\sqrt{a_i} - 1 \leq 0.
\tag{3}
$$
The parabola $y = x^2 - ix - 1$ lies below the $x$-axis for $1 \leq x \leq \frac{1}{2}\left(i + \sqrt{4 + i^2}\right)$, so equation $(3)$ combined with the assumption $a_i \geq 1$ yields
$$
1 \leq a_i \leq \left(\tfrac{i}{2} + \tfrac{1}{2}\sqrt{4 + i^2}\right)^2 \leq i^2 + 2,
$$
where the last inequality follows from Jensen's inequality.
$$
\tag*{$\square$}
$$

Claim: If $1 = a_1 \leq a_2 \leq a_3 \leq \cdots$ and $a_{i+1}-a_i \leq \sqrt{a_i}$ then
  $$
\sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} = O(\log n)
$$
  for all $n$.

Proof: The result is trivially true for $n=1$ so suppose $n \geq 2$. Combining Lemmas 1 and 2 yields
$$
0 \leq \sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} \leq C\log a_n \leq C\log(n^2+2) \leq D \log n
$$
for some constants $C$ and $D$.
$$
\tag*{$\square$}
$$

Intuition
The sum in question behaves in many ways like a "discrete logarithm", and in the sense of Lemma 1 we have something like
$$
\sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} \approx \log \frac{a_n}{a_1}.
$$
For example, if we double every term of the sequence $(a_n)$ then the values on both sides of the $\approx$ remain unchanged. Further, if $a_n$ is the constant sequence $a_n = a_1$ then both sides of the $\approx$ are equal.
(I'm not sure what the analogue of $\log xy = \log x + \log y$ would be.)
We could try to approach this problem by looking at the smooth analogues of the sequence and sum. The difference $a_{i+1} - a_i$ can be thought of as a discrete derivative and the sum as a discrete integral. So if we can find some function $f$ with $f(n) \approx a_n$ and
$$
f'(n) \approx a_{n+1} - a_n
$$
then we might expect that
$$
\sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} \approx \int_1^n \frac{f'(x)}{f(x)}\,dx = \log \frac{f(n)}{f(1)} \approx \log \frac{a_n}{a_1}.
$$
This observation was what lead me to the approach in this answer.
