Let $f$ be a continuous function and $[a,b]$ be an interval where $f(c)=0$ for some unique number $c \in [a,b]$ and where $f(a) f(b) \leq 0$. Suppose there exists a sub-interval $[a_0,b_0]\subset [a,b]$ so that $c \in [a_0,b_0]$ and some other function $g$ such that $g(x_1)=g(x_2)$ for all $x_1, x_2 \in [a_0, b_0]$. Also we know $g(x_1) \neq g(x_2)$ if $x_1 \ne x_2$ and either $x_1 \notin [a_0,b_0]$ or $x_2 \notin [a_0,b_0]$. We are not given the numbers $a_0$ and $b_0$.

Suppose we use the standard bisection method to find the root $c$ of $f$. However, we stop when $g(x_1)= g(x_2)$ for two numbers $x_1$ and $x_2$. In fact, the procedure terminates where we find an interval $[x_1, x_2] \subset [a_0, b_0]$ with $c \in [a_0,b_0]$.

Question: What is the complexity of the algorithm? Can we say the algorithm runs in polynomial time?

  • $\begingroup$ I don't understand the algorithm, or what you are trying to achieve. Can you provide the pseudocode for the algorithm? You say "we stop when $g(x_1)=g(x_2)$", but what are $x_1,x_2$? I don't understand the condition under which you stop, or why you would stop then. Also, when you ask about polynomial time -- polynomial in what? Are your numbers integers? Are they real numbers? if you're working with real numbers, standard models of computation aren't suitable -- you'll need to identify your model of computation, to make running time well defined. $\endgroup$ – D.W. Nov 8 '18 at 21:25
  • $\begingroup$ This question is about parametric linear programming where the parameter is in the right-hand side vector of constraints. However, I simplify the question avoid details. The interval $[a,b]$ consists of all real numbers. we can present the algorithm as follows: 1.While $g(a) \neq g(b)$ do compute $c=\frac{a+b}{2}$. If f(c)=0, then stop;Else if f(a)*f(c)<0; then b:=c; else a:=b EndWhile $\endgroup$ – A.R.S Nov 9 '18 at 10:15
  • $\begingroup$ Rather than responding in a comment, please edit the question to incorporate your pseudocode. We want questions to stand on their own, so people don't have to read the comment to understand what is being asked. Also, I still don't see an answer to my other questions (e.g., about model of computation, polynomial in what attribute, etc.). $\endgroup$ – D.W. Nov 9 '18 at 18:54

Your Answer

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

Browse other questions tagged or ask your own question.