time complexity

[ashu]

there is question :
What is the smallest value of n such that an algorithm whose running
time is 100n2 runs faster than an algorithm whose running time is 2n
on the same machine.

i can`t understand this question plz help me

[Keith Thompson]

Re: time complexity

ashu <ashishmourya21 @gmail.comwrite s:

there is question :
What is the smallest value of n such that an algorithm whose running
time is 100n2 runs faster than an algorithm whose running time is 2n
on the same machine.
>
i can`t understand this question plz help me

Ask your instructor for help. This is homework, right?

In any case, this isn't a question about the C programming language,
so I don't know why you're asking it here.

I also suspect you've quoted the question incorrectly. Is "100n2"
supposd to be 100 * n * n?

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Richard Heathfield]

Re: time complexity

Keith Thompson said:

ashu <ashishmourya21 @gmail.comwrite s:

>there is question :
>What is the smallest value of n such that an algorithm whose running
>time is 100n2 runs faster than an algorithm whose running time is 2n
>on the same machine.
>>
>i can`t understand this question plz help me

>
Ask your instructor for help. This is homework, right?
>
In any case, this isn't a question about the C programming language,
so I don't know why you're asking it here.
>
I also suspect you've quoted the question incorrectly. Is "100n2"
supposd to be 100 * n * n?

I expect so. And presumably 2n supposed to be 2 to the power n.

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. It may also be useful to realise
that, when n is set to the correct value, both 2 to the power n and 100 *
n * n easily fit in an unsigned long int. (Yes, I know, but I don't want
to be more specific than that, because it would give too much information;
what I have given, however, should enable the OP to recognise that this
problem can be solved with a very, very, very simple C program.)

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Dik T. Winter]

Re: time complexity

In article <Wr2dnQuAkstHkI ranZ2dneKdnZydn Z2d@bt.comrjh@see.sig.inv alid 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.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Richard Heathfield]

Re: time complexity

Dik T. Winter said:

In article <Wr2dnQuAkstHkI ranZ2dneKdnZydn Z2d@bt.comrjh@see.sig.inv alid
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.

It isn't? Using a simple iterative technique, I found the answer in nothing
flat (actually about 3 milliseconds), getting agreement in 2^n and 100n^2
to ten decimal places. Given that we only *need* it to one decimal place,
I'd have thought that was an adequate solution.

I suspect we are using different definitions of "mathematic al". :-)

<snip>

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Dik T. Winter]

Re: time complexity

In article <RYydnTSksuDDjY HanZ2dnUVZ8sOon Z2d@bt.comrjh@see.sig.inv alid writes:

Dik T. Winter said:
>

In article <Wr2dnQuAkstHkI ranZ2dneKdnZydn Z2d@bt.comrjh@see.sig.inv alid
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.

>
It isn't? Using a simple iterative technique, I found the answer in nothing
flat (actually about 3 milliseconds), getting agreement in 2^n and 100n^2
to ten decimal places. Given that we only *need* it to one decimal place,
I'd have thought that was an adequate solution.
>
I suspect we are using different definitions of "mathematic al". :-)

No. The difference is between finding a value and finding an approximation
to a value.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Richard Heathfield]

Re: time complexity

Dik T. Winter said:

In article <RYydnTSksuDDjY HanZ2dnUVZ8sOon Z2d@bt.comrjh@see.sig.inv alid
writes:

Dik T. Winter said:
>

In article <Wr2dnQuAkstHkI ranZ2dneKdnZydn Z2d@bt.com>
rjh@see.sig.inv alid 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.

>
It isn't? Using a simple iterative technique, I found the answer in
nothing flat (actually about 3 milliseconds), getting agreement in 2^n
and 100n^2 to ten decimal places. Given that we only *need* it to one
decimal place, I'd have thought that was an adequate solution.
>
I suspect we are using different definitions of "mathematic al". :-)

>
No. The difference is between finding a value and finding an
approximation to a value.

Fine. Bear in mind, however, that the final value in my original discussion
was an integer value, and it can of course be determined precisely.

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[CBFalconer]

Re: time complexity

Richard Heathfield wrote:

Dik T. Winter said:

>rjh@see.sig.inv alid 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.

>
It isn't? Using a simple iterative technique, I found the answer
in nothing flat (actually about 3 milliseconds), getting agreement
in 2^n and 100n^2 to ten decimal places. Given that we only *need*
it to one decimal place, I'd have thought that was an adequate
solution.

Taking log2() function of both sides, we have:

n = log2(100) + 2 * log2(n)

which makes it fairly easy to divide integers into two classes,
i.e. those where "n < log2(100) + 2*log2(n)" and those where "n >
log2(100) + 2*log2(n)". Note that the equality condition cannot
occur since 2 does not contain all the factors of 100. We can go
close to exactness by considering 100 as 2*2*5*5, so that log2(100)
= 2 + 2* log2(5), and that result is obviously greater than 6 and
less than 7.

All this should be obvious to any child of 10 who has passed the
kindergarten class on logarithms.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net>


--
Posted via a free Usenet account from http://www.teranews.com

[Richard Harter]

Re: time complexity

On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
<Dik.Winter@cwi .nlwrote:

>In article <RYydnTSksuDDjY HanZ2dnUVZ8sOon Z2d@bt.comrjh@see.sig.inv alid writes:

Dik T. Winter said:

In article <Wr2dnQuAkstHkI ranZ2dneKdnZydn Z2d@bt.comrjh@see.sig.inv alid
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.

It isn't? Using a simple iterative technique, I found the answer in nothing
flat (actually about 3 milliseconds), getting agreement in 2^n and 100n^2
to ten decimal places. Given that we only *need* it to one decimal place,
I'd have thought that was an adequate solution.

I suspect we are using different definitions of "mathematic al". :-)

>
>No. The difference is between finding a value and finding an approximation
>to a value.

And the computer on which you can express that value is?


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die

[user923005]

Re: time complexity

On Oct 22, 3:37 pm, c...@tiac.net (Richard Harter) wrote:

On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
>
>
>
>
>
<Dik.Win...@cwi .nlwrote:

In article <RYydnTSksuDDjY HanZ2dnUVZ8sOon ...@bt.comr...@ see.sig.invalid writes:

Dik T. Winter said:

>

In article <Wr2dnQuAkstHkI ranZ2dneKdnZydn ...@bt.comr...@ see.sig.invalid
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.

>

It isn't? Using a simple iterative technique, I found the answer in nothing
flat (actually about 3 milliseconds), getting agreement in 2^n and 100n^2
to ten decimal places. Given that we only *need* it to one decimal place,
I'd have thought that was an adequate solution.

>

I suspect we are using different definitions of "mathematic al". :-)

>

No. The difference is between finding a value and finding an approximation
to a value.

>
And the computer on which you can express that value is?

I'm not sure what all the fuss is about, it's a parabola, with roots
at 0.0 and 0.02.[*]
[*] which is, of course, utter bologna. Both equations have a
constant of proportionality , which means that the solution could be
any real number. (Assuming 2*n and not 2^n) ;-)

OK, maybe 1.432472784e+00 1 given some "other interpretation" . Give or
take a constant factor as large or small as you like.

P.S.
Keith Briggs has a nifty LambertW function on his web site (or used to
at least).

[user923005]

Re: time complexity

On Oct 22, 3:37 pm, c...@tiac.net (Richard Harter) wrote:

On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
>
>
>
>
>
<Dik.Win...@cwi .nlwrote:

In article <RYydnTSksuDDjY HanZ2dnUVZ8sOon ...@bt.comr...@ see.sig.invalid writes:

Dik T. Winter said:

>

In article <Wr2dnQuAkstHkI ranZ2dneKdnZydn ...@bt.comr...@ see.sig.invalid
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.

>

It isn't? Using a simple iterative technique, I found the answer in nothing
flat (actually about 3 milliseconds), getting agreement in 2^n and 100n^2
to ten decimal places. Given that we only *need* it to one decimal place,
I'd have thought that was an adequate solution.

>

I suspect we are using different definitions of "mathematic al". :-)

>

No. The difference is between finding a value and finding an approximation
to a value.

>
And the computer on which you can express that value is?

If you give it in terms of an equation, then you can easily accomplish
it symbolically.

[Richard Harter]

Re: time complexity

On Mon, 22 Oct 2007 18:17:01 -0700, user923005
<dcorbit@connx. comwrote:

>On Oct 22, 3:37 pm, c...@tiac.net (Richard Harter) wrote:

>On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
>>
>>
>>
>>
>>
><Dik.Win...@cw i.nlwrote:

>In article <RYydnTSksuDDjY HanZ2dnUVZ8sOon ...@bt.comr...@ see.sig.invalid writes:
Dik T. Winter said:

>>

In article <Wr2dnQuAkstHkI ranZ2dneKdnZydn ...@bt.comr...@ see.sig.invalid
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.

>>

It isn't? Using a simple iterative technique, I found the answer in nothing
flat (actually about 3 milliseconds), getting agreement in 2^n and 100n^2
to ten decimal places. Given that we only *need* it to one decimal place,
I'd have thought that was an adequate solution.

>>

I suspect we are using different definitions of "mathematic al". :-)

>>

>No. The difference is between finding a value and finding an approximation
>to a value.

>>
>And the computer on which you can express that value is?

>
>If you give it in terms of an equation, then you can easily accomplish
>it symbolically.
>

Granted. However Dik wrote "Finding the real value" which is not
the same thing as finding either an approximation or a symbolic
expression. In other words he was asking for something that
cannot be produced either by a computer or a human being, even
though it can be done by a mathematician.





Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die

[Dik T. Winter]

Re: time complexity

In article <471cba8d.10764 51937@news.sbtc .netcri@tiac.net (Richard Harter) writes:

On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
<Dik.Winter@cwi .nlwrote:

....

I suspect we are using different definitions of "mathematic al". :-)

No. The difference is between finding a value and finding an approximation
to a value.

>
And the computer on which you can express that value is?

Strange, I thought that in a previous article I gave that value.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Dik T. Winter]

Re: time complexity

In article <1193102160.153 163.56110@e9g20 00prf.googlegro ups.comuser9230 05 <dcorbit@connx. comwrites:

On Oct 21, 7:32 pm, "Dik T. Winter" <Dik.Win...@cwi .nlwrote:

In article <Wr2dnQuAkstHkI ranZ2dneKdnZydn ...@bt.comr...@ see.sig.invalid writes:

....

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.

I had gone off somewhere. The actual solution is:
sqrt(exp(-W(-log(2)/20)))/10.

Note however, that if you take the principal value of the W function
the result is 0.1036578164 (which is indeed also a solution). You
need the value on another branch. In Maple that would be
sqrt(exp(Lamber tW(-1, -log(2)/20)))/10.
and then you get:

14.32472784

approximately.

(Yes, it is not trivial...)
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Richard Harter]

Re: time complexity

On Tue, 23 Oct 2007 10:32:01 GMT, "Dik T. Winter"
<Dik.Winter@cwi .nlwrote:

>In article <471cba8d.10764 51937@news.sbtc .netcri@tiac.net (Richard Harter) writes:

On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
<Dik.Winter@cwi .nlwrote:

>...

I suspect we are using different definitions of "mathematic al". :-)
>
>No. The difference is between finding a value and finding an approximation
>to a value.

And the computer on which you can express that value is?

>
>Strange, I thought that in a previous article I gave that value.

Well, no, you gave an expression that would yield the value if
evaluated with infinite precision. Not at all the same thing as
the real value.



Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die