Discussion: time complexity
Afficher un message
Vieux 22/10/2007, 03h32   #4
Dik T. Winter
Aucun Avatar
 
Messages: n/a
Hébergeur:
Par défaut Re: time complexity

In article <Wr2dnQuAkstHkIranZ2dneKdnZydnZ2d@bt.com> rjh@see.sig.invalid writes:
....
> It may 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.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
  Réponse avec citation
 
Page generated in 0,06441 seconds with 9 queries