patternMinor
What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?
Viewed 0 times
depththeeachrecursionwhatarrayintowithlog_2call
Problem
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.
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.
Solution
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}.
$$
$$
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}.
$$
Context
StackExchange Computer Science Q#103508, answer score: 5
Revisions (0)
No revisions yet.