Velocity Reviews > time complexity

# time complexity

ashu
Guest
Posts: n/a

 10-18-2007
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
Guest
Posts: n/a

 10-18-2007
ashu <(E-Mail Removed)> 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 help me

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) http://www.velocityreviews.com/forums/(E-Mail Removed) <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
Guest
Posts: n/a

 10-18-2007
Keith Thompson said:

> ashu <(E-Mail Removed)> 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 help me

>
>
> 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@
"Usenet is a strange place" - dmr 29 July 1999

Dik T. Winter
Guest
Posts: n/a

 10-22-2007
In article <(E-Mail Removed)> (E-Mail Removed)lid 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
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
Guest
Posts: n/a

 10-22-2007
Dik T. Winter said:

> In article <(E-Mail Removed)> (E-Mail Removed)lid
> 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 "mathematical".

<snip>

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

CBFalconer
Guest
Posts: n/a

 10-22-2007
Richard Heathfield wrote:
> Dik T. Winter said:
>> (E-Mail Removed)lid 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

Dik T. Winter
Guest
Posts: n/a

 10-22-2007
In article <(E-Mail Removed)> (E-Mail Removed)lid writes:
> Dik T. Winter said:
>
> > In article <(E-Mail Removed)> (E-Mail Removed)lid
> > 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 "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/

Richard Heathfield
Guest
Posts: n/a

 10-22-2007
Dik T. Winter said:

> In article <(E-Mail Removed)> (E-Mail Removed)lid
> writes:
> > Dik T. Winter said:
> >
> > > In article <(E-Mail Removed)>
> > > (E-Mail Removed)lid 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 "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@
"Usenet is a strange place" - dmr 29 July 1999

Richard Harter
Guest
Posts: n/a

 10-22-2007
On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
<(E-Mail Removed)> wrote:

>In article <(E-Mail Removed)> (E-Mail Removed)lid writes:
> > Dik T. Winter said:
> >
> > > In article <(E-Mail Removed)> (E-Mail Removed)lid
> > > 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 "mathematical".

>
>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, (E-Mail Removed)
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
Guest
Posts: n/a

 10-23-2007
On Oct 22, 3:37 pm, (E-Mail Removed) (Richard Harter) wrote:
> On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
>
>
>
>
>
> <(E-Mail Removed)> wrote:
> >In article <(E-Mail Removed)> (E-Mail Removed) writes:
> > > Dik T. Winter said:

>
> > > > In article <(E-Mail Removed)> (E-Mail Removed)
> > > > 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 "mathematical".

>
> >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+001 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).