Reduce the running by using doubly logarithmic tree

Question

I have two algorithms $A$ and $B$ to solve a problem $P$ of size $n$. Algorithm $A$ takes $O(\log n)$ time on the PRAM using $O(n \log n)$ operations (done in parallel). Algorithm $B$ reduces the size of $P$ by a constant factor in $O(\log n/ \log \log n)$ time using $O(n)$ operations (also done in parallel). Can I solve problem $P$ using $O(n)$ operations in $O(log n)$ time? I feel it can be done using a doubly logarithmic tree (not sure).

Answer 1

I will assume you are using parallel processing to achieve the advertised runtimes. Say algorithm B scales the size of P by a factor $c<1$. If we apply algorithm B $k$ times, the size of our problem will be $c^kn$. This will require time $$\sum_{i=0}^{k-1}O(\log(c^in)/\log(\log(c^in)))=\sum_{i=0}^{k-1}O\left(\frac{i\log c+\log n}{\log(i\log c+\log n)}\right)$$ and $$\sum_{i=0}^{k-1}O(c^in)=O\left(\frac{1-c^k}{1-c}n\right)$$ operations. Then an application of algorithm A will require $O(\log(c^kn))=O(k\log c+\log n)$ time with $O(c^kn\log(c^kn)=O(c^kn(k\log c+\log n))$ operations. For the overall operations to be $O(n)$, we need $$\frac{1-c^k}{1-c}+c^k(k\log c+\log n)=O(1)$$ The only way for this to be constant with the $c^k\log n$ term is if $k$ depends on $n$. Then the $c^kk\log c$ term will shrink with $n$, since $\log c<0$. Taking $c^k=\frac{N}{\log n}$ for some positive constant $N$ gives $$\frac{1}{1-c}-\frac{N}{(1-c)\log n}-\frac{N(\log \log n-\log N)}{\log n}+N=O(1)$$ As $n$ grows, we can see that this approaches $(1-c)^{-1}+N=O(1)$ from below. Plugging this into the expression for the runtime (sum of both parts) gives $$O(\log n+\log N-\log \log n)+\sum_{i=0}^{k-1}O\left(\frac{i\log c+\log n}{\log(i\log c+\log n)}\right)$$ Since $\log c<0$, we can make the sum larger by doing $i\log c=k\log c$ on the bottom to get $$O(\log n)+O\left(\frac{\frac{k(k-1)}{2}\log c+k\log n}{\log(k\log c+\log n)}\right)$$ Substituting the earlier expression for $k$ gives $$O(\log n)+O\left(\frac{\substack{-\log (c) \log (N)+\log (c) \log (\log (n))+2 \log (N) \log (n)\\-2 \log (N) \log (\log (n))+\log ^2(N)+\log ^2(\log (n))-2 \log (n) \log (\log (n))}}{2 \log (c) \log (\log (N)+\log (n)-\log (\log (n)))}\right)$$ which simplifies to $$O(\log n)+O\left(\frac{\log n \log \log n}{-\log (c) \log (\log (N)+\log (n)-\log (\log (n)))}\right)$$ giving $O(\log n)$. That was tedious. Don't ask about the intermediate steps, I used the Wolfram Cloud.