Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > time complexity

Reply
Thread Tools

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

 
Reply With Quote
 
 
 
 
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


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_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"
 
Reply With Quote
 
 
 
 
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

>
> 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
 
Reply With Quote
 
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
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/
 
Reply With Quote
 
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@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
 
Reply With Quote
 
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

 
Reply With Quote
 
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/
 
Reply With Quote
 
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@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
 
Reply With Quote
 
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
 
Reply With Quote
 
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).

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Time Complexity of String Operations youtoo Python 3 07-22-2008 12:17 PM
time complexity dondora C++ 2 09-16-2007 11:58 PM
Time complexity of size() for std::set Lionel B C++ 26 02-03-2007 11:21 PM
Time Complexity davide.sammartino@gmail.com C Programming 9 07-11-2006 08:26 PM
How to calculate the time Complexity? codergem@gmail.com C++ 2 06-12-2006 05:17 AM



Advertisments