What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

Question

We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there are only two elements left in it. What is the depth of this recursion?

Example of the process:

First we have $n$ elements and break them up into $\log_2(n)$ parts with equal sizes. Each of these parts has $\frac {n} {log_2(n)}$ elements in it. In the next level of recursion we will break each of the subarrays into $log_2(\frac {n} {log_2(n)})$ parts again with equal sizes. These will now have $\frac {\frac {n} {log_2(n)}} {log_2(\frac {n} {log_2(n)})}$ elements in each one of them. And we keep on breaking the array in this manner until we reach a subarray with only two elements in it.

Answer 1

Let $f(n) = n/\log n$, and denote by $g(n)$ the number of applications of $f$ it takes to get $n$ below some arbitrary constant. On the one hand, $f^{(t)}(n) \geq n/\log^t n$, and so $$ g(n) \geq \log_{\log n} n = \frac{\log n}{\log \log n}. $$ To obtain an upper bound, notice that as long as $f^{(t)}(n) \geq \sqrt{n}$, we have $\log f^{(t)}(n) \geq (\log n)/2$, and so it takes at most $\log_{(\log n)/2} n = O(\log n/\log\log n)$ iterations to reduce $n$ to $\sqrt{n}$. The same argument applies for reducing $\sqrt{n}$ to $\sqrt[4]{n}$ and so on, and therefore $$ g(n) \ll \frac{\log n}{\log\log n} + \frac{\log \sqrt{n}}{\log\log \sqrt{n}} + \frac{\log \sqrt[4]{n}}{\log\log \sqrt[4]{n}} + \cdots. $$ (Here $\cdot \ll \cdot$ is the same as $\cdot = O(\cdot)$.) Notice that $\log \sqrt{n} = \frac{1}{2} \log n$. For large $n$, we will have $\log\log \sqrt{n} \geq \frac{2}{3} \log \log n$ (say), and so $$ \frac{\log \sqrt{n}}{\log\log \sqrt{n}} \leq \frac{2}{3} \frac{\log n}{\log\log n}. $$ Therefore the sum is majorized by a convergent geometric series, and we conclude that $$ g(n) = O\left(\frac{\log n}{\log\log n}\right). $$ In total, we get that $$ g(n) = \Theta\left(\frac{\log n}{\log \log n}\right). $$ With more work, we can probably prove a more refined estimate such as $$ g(n) \sim \frac{\log n}{\log \log n}. $$

Answer 2

Seems that you are refering to iterated logarithm, also know as the $log *$ function. It is a function that expresses how many times you can take the logarithm of a number until it produces a number less than or equals to 1.

The $log*$ function grows very slowly. It is the inverse of tetration.

See more of that here.

Answer 3

Let n be the size of the array. Let k = log2 (n). At the first step, you divide by k. As long as the array size is more than $n^{1/2}$, you divide by more than k/2. I'd say this is O (log n / log log n).

(Always splitting into k parts takes log n / log k splits. You asked for the special case k = log n, therefore log n / log log n. Then you need to decide whether the shrinking k makes a difference or not. )

Answer 4

All logarithm below means logarithm with base 2, $\log_2(\cdot)$.

---

Let us name the function given in the question $\operatorname{slog}$. ("slog" comes from splitting with log. It can also imply "smaller than log".) In precise terms, $\operatorname{slog}$ on $\Bbb N$ is defined by the following conditions.

• base case, $\operatorname{slog}(1)=0$ and $\operatorname{slog}(2)=1.$
• the recurrence relation, $\operatorname{slog}(n)=1+ \text{slog}\left(\left\lceil\dfrac{n}{ \lceil\log n\rceil}\right\rceil\right)$ for $n\gt2.$

We can prove the following proposition on the asymptotic behavior of $\operatorname{slog}(n)$. $$\lim_{n\to\infty}\dfrac{\quad\text{ slog}(n)\quad}{\dfrac{\log n}{\log\log n}}=1.$$

Here is the basic idea of the proof.

$$\begin{align} \lim_{n\to\infty}\frac{\log n}{\log\log n}-\frac{\log \frac n{\log n}}{\log\log \frac n{\log n}} &=\lim_{m\to\infty}\frac{m}{\log m}-\frac{m-\log m}{\log(m-\log m)}\\ &=\lim_{m\to\infty}\frac{m}{\log m}-\frac{m-\log m}{\log m + \log(1- \frac{\log m}m)}\\ &=\lim_{m\to\infty}\frac{(\log m)^2+ m\log(1- \frac{\log m}m)}{(\log m)(\log m+ \log(1- \frac{\log m}m))}\\ &=\lim_{m\to\infty}\frac{(\log m)^2+ m(-\frac{\log m}m)}{(\log m)(\log m)}\\ &=1 \end{align}$$

Corollary. $\text{slog}(n)=\Theta\left(\dfrac{\log n}{\log\log n}\right)$.

---

The same conclusion holds if we define $\text{slog}(x)$ for $x>1$ with $\text{slog}(x)=1$ for $1\lt x\le 2$ and $\operatorname{slog}(n)=1+ \text{slog}\left(\dfrac{n}{ \log n}\right)$.

---

Exercise. Write the full proof of $\text{slog}(n)\sim \dfrac{\log n}{\log\log n}$.