# Run-time analysis of distributed network decomposition algorithm

I'm trying to understand the run-time analysis in the article [1].

The authors define the following notation: $g(n) = \hat O(f(n))$ if $g(n) = O(f(n)^{O(1)})$. In the run-time analysis of their algorithm, they find that $$T(l) \leq \hat O(p\log n)10^{\log_{p/2} l} \equiv f(l,p)$$ where $n$ is the number of nodes in the network, $l$ is the number of nodes in the input to the (recursive) algorithm and $p$ is a parameter.

Then they claim that the minimum of $f(n,p)$ is attained when $p=2^{\Theta(\sqrt{\log n})} = \hat O(n^{\epsilon(n)})$ with $\epsilon(n) = \frac 1{\sqrt{\log n}}$. This is the part that I don't understand. How do you minimize $f(n,p)$?

1. On the Complexity of Distributed Network Decomposition by A. Panconesi and A. Srinivasan (1996)

Calculus: any local minimum of the function $f(x)$ must be a point $x$ that satisfies $f'(x)=0$, where $f'(x)$ is the first derivative of $f(x)$. So, take the derivative, set it to zero, and find all solutions. Each solution is a candidate for the minimum. You then need to check each candidate to see which makes $f(x)$ smallest. You'll also need to check the "endpoints", e.g., the smallest and largest possible value for $x$ need to be added as candidates.
• @ItayPerl, same way. To minimize $\Theta(f(x))$, minimize $f(x)$. – D.W. Dec 14 '15 at 1:00