Re: time complexity

On Oct 21, 7:32 pm, "Dik T. Winter" <Dik.Win...@xxxxxx> wrote:
In article <Wr2dnQuAkstHkIranZ2dneKdnZydn...@xxxxxx> r...@xxxxxxxxxxxxxxx writes:

...
> It may help the OP to recognise that the question, as asked (i.e. in the
> absence of big-O notation, which IMHO would in any case make the question
> meaningless), is looking for the integer value of n that is just higher
> than the real value that is the solution to the following equation:
>
> 2 to the power n = 100 * n * n
>
> This is a simple mathematical exercise.

Finding the real value is not exactly a simple mathematical exercise. The
answer includes Lambert's W-function... Actually, finding the answer to
the actual question is not a mathematical exercise at all, just plug in
numbers until you get the answer. Off-hand I have no idea how to formulate
the mathematical answer, but I think it is:
ceiling(exp(-W(-2*log(log(2)/100)/2)))
where W is Lambert's W-function. But I can be wrong, if you have
mathematica on your computer, you can check it.

I must have gone off somewhere.

y:= 100 * n * n - 2 ^ n;

2 n
y := 100 n - 2

fsolve(y, n, -1..100);

14.32472784

plot(y, n = 5..16);


z := (exp(-LambertW(-2*log(log(2)/100)/2))) ;

z := exp(-LambertW(-ln(1/100 ln(2))))

evalf(");

.2662051936



I got the same answer with this:

/*

************************************************************************
* C math library
* function ZEROIN - obtain a function zero within the given range
*
* Input
* double zeroin(ax,bx,f,tol)
* double ax; Root will be seeked for within
* double bx; a range [ax,bx]
* double (*f)(double x); Name of the function whose
zero
* will be seeked for
* double tol; Acceptable tolerance for the
root
* value.
* May be specified as 0.0 to
cause
* the program to find the root
as
* accurate as possible
*
* Output
* Zeroin returns an estimate for the root with accuracy
* 4*EPSILON*abs(x) + tol
*
* Algorithm
* G.Forsythe, M.Malcolm, C.Moler, Computer methods for
mathematical
* computations. M., Mir, 1980, p.180 of the Russian edition
*
* The function makes use of the bissection procedure combined
with
* the linear or quadric inverse interpolation.
* At every step program operates on three abscissae - a, b, and
c.
* b - the last and the best approximation to the root
* a - the last but one approximation
* c - the last but one or even earlier approximation than a that
* 1) |f(b)| <= |f(c)|
* 2) f(b) and f(c) have opposite signs, i.e. b and c
confine
* the root
* At every step Zeroin selects one of the two new
approximations, the
* former being obtained by the bissection procedure and the
latter
* resulting in the interpolation (if a,b, and c are all
different
* the quadric interpolation is utilized, otherwise the linear
one).
* If the latter (i.e. obtained by the interpolation) point is
* reasonable (i.e. lies within the current interval [b,c] not
being
* too close to the boundaries) it is accepted. The bissection
result
* is used in the other case. Therefore, the range of uncertainty
is
* ensured to be reduced at least by the factor 1.6
*

************************************************************************
*/

#include <math.h>
#include <stdio.h>
#include <float.h>

/* An estimate to the root */
/* ax Left border | of the range */
/* bx Right border| the root is seeked */
/* f() Function under investigation */
/* tol Acceptable tolerance */
double zeroin(double ax, double bx, double (*f) (double),
double tol)
{
double a,
b,
c; /* Abscissae, descr. see above */
double fa; /* f(a) */
double fb; /* f(b) */
double fc; /* f(c) */

if (tol < 0) {
tol = -tol;
puts("negative tol not allowed. Using abs(tol)");
}
if (bx < ax) {
double tmp = bx;
bx = ax;
ax = tmp;
puts("interval was reversed. Using [bx, ax] instead of [ax,
bx]");
}
a = ax;
b = bx;
fa = (*f) (a);
fb = (*f) (b);
c = a;
fc = fa;
/* Main iteration loop */
for (;;) {
/* Distance from the last but one to the last approximation */
double prev_step = b - a;
double tol_act;/* Actual tolerance */
double p; /* Interpolation step is calcu- */
double q; /* lated in the form p/q; divi- */
/* sion operations is delayed */
/* until the last moment */
double new_step; /* Step at this iteration */

if (fabs(fc) < fabs(fb)) { /* Swap data for b to be the
*/
a = b;
b = c;
c = a; /* best approximation */
fa = fb;
fb = fc;
fc = fa;
}
tol_act = 2 * DBL_EPSILON * fabs(b) + tol / 2;
new_step = (c - b) / 2;

/* BUGBUG: DRC --------------------------------------- */
/* Here, testing a double for equality is a good idea. */
/* BUGBUG: DRC --------------------------------------- */
if (fabs(new_step) <= tol_act || fb == 0.0)
return b; /* Acceptable approx. is found */

/* Decide if the interpolation can be tried */
if (fabs(prev_step) >= tol_act /* If prev_step was large
enough */
&& fabs(fa) > fabs(fb)) { /* and was in true direction,
*/
/* Interpolatiom may be tried */
register double t1,
cb,
t2;
cb = c - b;
/* If only two distinct points, linear interpolation */
/* can only be applied. */
/* BUGBUG: DRC ------------------------------------------
*/
/* This test for equality is questionable. If very, very
*/
/* close to linear, we may have large calculation errors.
*/
/* (Or so it seems to me). Perhaps Dik Winter can help.
*/
/* BUGBUG: DRC ------------------------------------------
*/
if (a == c) {
t1 = fb / fa;
p = cb * t1;
q = 1.0 - t1;
} else { /* Quadric inverse interpolation */
q = fa / fc;
t1 = fb / fc;
t2 = fb / fa;
p = t2 * (cb * q * (q - t1) - (b - a) * (t1 - 1.0));
q = (q - 1.0) * (t1 - 1.0) * (t2 - 1.0);
}
if (p > 0.0) /* p was calculated with the op- */
q = -q; /* posite sign; make p positive */
else /* and assign possible minus to */
p = -p; /* q */

/* If b+p/q falls in [b,c] and isn't too large it is
accepted */
if (p < (0.75 * cb * q - fabs(tol_act * q) / 2)
&& p < fabs(prev_step * q / 2))
new_step = p / q;
/* If p/q is too large then the bissection procedure can
*/
/* reduce [b,c] range further */
}
if (fabs(new_step) < tol_act) /* Adjust the step to be not
less */
if (new_step > (double) 0) /* than tolerance */
new_step = tol_act;
else
new_step = -tol_act;
a = b;
fa = fb; /* Save the previous approx. */
b += new_step;
fb = (*f) (b); /* Do step to a new approxim. */

/* Adjust c for it to have a sign opposite to that of b */
if ((fb > 0 && fc > 0) || (fb < 0 && fc < 0)) {
c = a;
fc = fa;
}
}
}
#ifdef UNIT_TEST
/*

*=======================================================================
* Verify ZEROIN routine
*/
double zeroin(double ax, double bx, double (*f) (double),
double tol);

static int counter; /* Iteration counter */

/* Run a test. */
/* [a,b]=interval containing a root (sign change) */
/* f = function */
/* msg = explanation message */
static void testz(double a, double b, double (*f) (double), char
*msg)
{
double root;
counter = 0;
printf("\nFor function %s\nin [%g,%g] root is\t%.9e\n", msg, a, b,
(root = zeroin(a, b, f, 0.0)));
printf("Function value at the root found\t%.4e\nNo. of iterations\t
\t%d\n",
(*f) (root), counter);
}

static double f1(double x)
{ /* test of the Forsythe book */
counter++;
return (x*x - 2.0) * x - 5.0;
}

static double f2(double x)
{ /* My test */
counter++;
return cos(x) - x;
}

static double f3(double x)
{ /* My test */
counter++;
return sin(x) - x;
}

static double f4(double x)
{ /* My test */
x = 0.17875/(1-0.05/x*(1-exp(-7*x)))-0.164-x;
return x;
}

static double f5(double x)
{ /* My test */
return 100.0 * x * x - pow(2.0, x);
}

int main(void)
{
puts("testing zero finder.");
testz(2.0, 3.0, f1, "x^3 - 2*x - 5");
printf("Exact root is \t\t2.0945514815\n");

testz(2.0, 3.0, f2, "cos(x)-x");
testz(-1.0, 3.0, f2, "cos(x)-x");
testz(-1.0, 3.0, f3, "sin(x)-x");
testz(-1.e29, 1e30, f4, "0.17875/(1-0.05/x*(1-exp(-7*x)))-0.164-
x");
testz(-10.0, 10000.0, f5, "100 * n * n - 2 ^ n");
return 0;
}
#endif


.

Relevant Pages

  • Re: cube root of a given number
    ... ROOT-SOLVING METHOD for computing, say, THE FIFHT ROOT OF 2. ... sheer luck if a best approximation was found. ... to scrutiny." ... remarks you have made in this posting. ...
    (sci.math)
  • Re: cube root of a given number
    ... ROOT-SOLVING METHOD for computing, say, THE FIFHT ROOT OF 2. ... sheer luck if a best approximation was found. ... to scrutiny." ... remarks you have made in this posting. ...
    (sci.math)
  • Re: Game Tree Programming Idea: Selectivity via modified alpha-beta pruning
    ... returns a score of 1.00 up to the root. ... idea will be good for alpha beta too. ... One can quite easily conclude that if you do this approximation (by ... root is no more than K * delta. ...
    (rec.games.chess.computer)
  • Re: cube root of a given number
    ... ROOT-SOLVING METHOD for computing, say, THE FIFHT ROOT OF 2. ... Form the mediant ... you can use your methods for simultaneous approximation of ... sheer luck if a best approximation was found. ...
    (sci.math)
  • find roots on uqtaion
    ... I would be grateful if you could help me with this basic question as I am very new to MATLAB. ... if abs< tol ... root = NaN; ...
    (comp.soft-sys.matlab)