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)

1 Answer 1


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.

You can do the same for functions of two variables, and for asymptotics.

  • $\begingroup$ How do you handle the asymptotics? $\endgroup$
    – Itay Perl
    Commented Dec 12, 2015 at 11:48
  • $\begingroup$ @ItayPerl, same way. To minimize $\Theta(f(x))$, minimize $f(x)$. $\endgroup$
    – D.W.
    Commented Dec 14, 2015 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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