# Reduce the running by using doubly logarithmic tree

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).

• It is not possible to use O(log n) time with O(n log n) operations unless using parallel processing. Please correct the question – HackerBoss Oct 11 '18 at 1:06

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.