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.

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

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

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.