Sorry if the terms I'm going to use is not professional enough:) This is about the complexity analysis of an algorithm.

Let $\alpha$ be the greatest real root of the polynomial $f(x)=x^n-2x^{n-1}-x^{n-k}-2^k$, in which $k$ is a parameter.

The question is how to choose $k$, $(k=\beta n, 0<\beta<1)$ in order to minimize $\alpha$?

We believe that $g$ exists because to minimize $\alpha$, the term $2^k$ requires a small $k$ while the rest needs a big $k$.

Thank you in advance for any idea.

We've just updated the recurrence relation, the idea is still the same. $k$ is still a relative value to $n$. Let $k=\beta n$. Then the new recurrence is
$f(x)=x^n-3x^{n-1}+x^{n-2}-x^{n-\beta n}-3^{\beta n}+3^{\beta (n-1)}$ Perhaps we can get more information from this one?

  • $\begingroup$ If you differentiate with respect to $k$ the relation $f(\alpha(k))=0$ and require $\alpha'(k)=0$, you obtain $k=\frac{\ln\frac{\ln\alpha(k)}{\ln2}+n\ln\alpha(k)}{\ln\alpha(k)-\ln 2}$. Don't know if that helps, though, but it may if you have some kind of control on $\alpha$ as the largest root. $\endgroup$ – Loïc Teyssier Apr 24 '15 at 9:36
  • $\begingroup$ Since you say "polynomial", is $k$ to be an integer $\le n$? By "largest" do you mean largest in absolute value, or greatest real root, or what? $\endgroup$ – Robert Israel Apr 24 '15 at 22:16
  • $\begingroup$ @RobertIsrael Sorry for the inaccuracy:) $k$ is an integer less than $n$, we may suppose $k=\beta n$ with $0<\beta<1$. By "largest", I mean greatest real root. $\endgroup$ – Leo Apr 28 '15 at 7:46

Let's write the function as $f(x,k)$.

For $k = 0$, the polynomial $f(x,0) = - 2 x^{n-1} - 1$ has no positive roots. For $k = 1$, $f(x,1) = x^n - 3 x^{n-1} - 2$ has a real root greater than $3$. For $k = 2$, $f(x,2) = x^{n-2} (x^2 - 2 x - 1) - 4 > 0$ if $x \ge 3$ and $n \ge 3$. For $k = n$, $f(x,n) = x^{n-1}(x - 2) - 1 - 2^n > 0$ if $x \ge 3$ and $n \ge 3$. Now $f(x,k)$ is a concave function of $\log_2(k)$ for fixed $x > 1$, so $f(x,k) > 0$ if $x \ge 3$, $n \ge 3$ and $2 \le k \le n$. Thus if $n \ge 3$, the greatest real root of $f(x,k)$ for integers $0 \le k \le n$ occurs at $k=1$.

Since the companion matrix of the polynomial $f(x,k)$ has nonnegative entries, the Perron-Frobenius theorem shows that the greatest real root is also the greatest in absolute value.

If we plot the roots, the picture is rather striking. Here is an animation showing the case $n=100$. For each $k\ge 1$ it appears that we have one positive root (near $x=3$ for $k=1$, decreasing rapidly to near $2$, and finally increasing slightly for $90 < k \le 100$), the other roots almost in a circle centred at $0$, of radius less than the real root, that expands as $k$ increases.

enter image description here

  • $\begingroup$ Thank you for your answer which reminds me to perform more experiments to explore properties. Do you mind to tell me what are the tools you use to find roots programmatically and also to visualize them? Thanks. $\endgroup$ – Leo Apr 28 '15 at 8:50
  • $\begingroup$ I used Maple to do this. $\endgroup$ – Robert Israel Apr 28 '15 at 19:35

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.