1
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.