Prev: Call for participants
Next: (paypal payment) wholesale Lacoste shirts from china,and free shipping
From: Chad on 8 May 2010 16:07
The question is about the harmonic() function in the following
code....

#include <stdio.h>

double harmonic(unsigned long n)
{
double acc = 0;
int i;

for (i = 1; i <= n; i++) {
acc += 1.0/i;
}

return acc;
}

int main(void)
{
unsigned long s;

printf("The value is: %g\n", harmonic(10));

return 0;
}


Would this function run in linear time? Just curious, because for
whatever reasons, I keep thinking that this runs in logarithmic time.
From: Ben Pfaff on 8 May 2010 16:15
Chad <cdalten(a)gmail.com> writes:

> double harmonic(unsigned long n)
> {
> double acc = 0;
> int i;
>
> for (i = 1; i <= n; i++) {
> acc += 1.0/i;
> }
>
> return acc;
> }
[...]
>
> Would this function run in linear time? Just curious, because for
> whatever reasons, I keep thinking that this runs in logarithmic time.

It performs n computation steps so it takes O(n) time.
--
"GNU does not eliminate all the world's problems,
only some of them."
--Richard Stallman
From: Kai-Uwe Bux on 8 May 2010 16:28
Chad wrote:

> The question is about the harmonic() function in the following
> code....
>
> #include <stdio.h>
>
> double harmonic(unsigned long n)
> {
> double acc = 0;
> int i;
>
> for (i = 1; i <= n; i++) {
> acc += 1.0/i;
> }
>
> return acc;
> }

Hint: summing up the terms in reverse order (starting with the smallest)
handles rounding errors much better and is numerically preferable.

> int main(void)
> {
> unsigned long s;
>
> printf("The value is: %g\n", harmonic(10));
>
> return 0;
> }
>
>
> Would this function run in linear time?

Well, it's linear in n. However, that is not the usual measure of run-time
complexity in computer science. The usual measure is to express the run-time
of an algorithm as it depends on the _length_ (number of bits) of the input.

> Just curious, because for
> whatever reasons, I keep thinking that this runs in logarithmic time.

That not correct either. It's exponential in the bit-length of n: if n has k
bits, the worst case is n = 2^k - 1, in which case, the for loop is
traversed about 2^k times. Thus, the run-time is O(2^k).


Best

Kai-Uwe Bux
From: Chad on 8 May 2010 18:32
On May 8, 1:28 pm, Kai-Uwe Bux <jkherci...(a)gmx.net> wrote:
> Chad wrote:
> > The question is about the harmonic() function in the following
> > code....
>
> > #include <stdio.h>
>
> > double harmonic(unsigned long n)
> > {
> >   double acc = 0;
> >   int i;
>
> >   for (i = 1; i <= n; i++) {
> >     acc += 1.0/i;
> >   }
>
> >   return acc;
> > }
>
> Hint: summing up the terms in reverse order (starting with the smallest)
> handles rounding errors much better and is numerically preferable.
>
> > int main(void)
> > {
> >   unsigned long s;
>
> >   printf("The value is: %g\n", harmonic(10));
>
> >   return 0;
> > }
>
> > Would this function run in linear time?
>
> Well, it's linear in n. However, that is not the usual measure of run-time
> complexity in computer science. The usual measure is to express the run-time
> of an algorithm as it depends on the _length_ (number of bits) of the input.
>
> > Just curious, because for
> > whatever reasons, I keep thinking that this runs in logarithmic time.
>
> That not correct either. It's exponential in the bit-length of n: if n has k
> bits, the worst case is n = 2^k - 1, in which case, the for loop is
> traversed about 2^k times. Thus, the run-time is O(2^k).
>

Okay, to my defense though, I'm not a Computer Scientist. The extent
of my "formal" computer training 6 weeks of FORTRAN and an
Introduction to C++. I thought about going back to school for Computer
Science, but I've had to reconsider this career move since San
Francisco State University, ie a school that pretty much will accept
anyone, rejected me.

From: Chad on 8 May 2010 19:04
On May 8, 1:28 pm, Kai-Uwe Bux <jkherci...(a)gmx.net> wrote:
> Chad wrote:
> > The question is about the harmonic() function in the following
> > code....
>
> > #include <stdio.h>
>
> > double harmonic(unsigned long n)
> > {
> >   double acc = 0;
> >   int i;
>
> >   for (i = 1; i <= n; i++) {
> >     acc += 1.0/i;
> >   }
>
> >   return acc;
> > }
>
> Hint: summing up the terms in reverse order (starting with the smallest)
> handles rounding errors much better and is numerically preferable.
>

Why would summing up the terms in reverse order handle rounding errors
much better?
 |  Next  |  Last
Pages: 1 2 3
Prev: Call for participants
Next: (paypal payment) wholesale Lacoste shirts from china,and free shipping