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 me

ashu <ashishmourya21@gmail.com> writes:
> 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 me

Ask your instructor for . 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_Keith) 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"

Keith Thompson said:

> ashu <ashishmourya21@gmail.com> writes:
>> 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 me
>
> Ask your instructor for . 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 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

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/

Dik T. Winter said:

> 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.

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 "mathematical". :-)

<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

Richard Heathfield wrote:
> Dik T. Winter said:
>> 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.
>
> 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

In article <RYydnTSksuDDjYHanZ2dnUVZ8sOonZ2d@bt.com> rjh@see.sig.invalid writes:
> Dik T. Winter said:
>
> > 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.
>
> 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 "mathematical". :-)

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/

Dik T. Winter said:

> In article <RYydnTSksuDDjYHanZ2dnUVZ8sOonZ2d@bt.com> rjh@see.sig.invalid
> writes:
> > Dik T. Winter said:
> >
> > > 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.
> >
> > 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 "mathematical". :-)
>
> 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