Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #5348 > unrolled thread

this problem comes from chapter 1 of introduction to algorithms

Back to article view | Back to comp.programming

Contents

  this problem comes from chapter 1 of introduction to algorithms G G <gdotone@gmail.com> - 2015-03-23 20:53 -0700
    Re: this problem comes from chapter 1 of introduction to algorithms Richard Heathfield <rjh@cpax.org.uk> - 2015-03-24 07:25 +0000
    Re: this problem comes from chapter 1 of introduction to algorithms Kaz Kylheku <kaz@kylheku.com> - 2015-03-24 14:29 +0000
      Re: this problem comes from chapter 1 of introduction to algorithms G G <gdotone@gmail.com> - 2015-03-24 14:25 -0700

#5348 — this problem comes from chapter 1 of introduction to algorithms

this would be for the first entry in the table

1-1 Comparison of running times
For each function f(n) and time t in the following table,
 determine the largest size n of a problem that can be 
solved in time t, assuming that the algorithm to solve 
the problem takes f(n) microseconds.

f(n) = lg n       time = 1 second

am i thinking about this correctly. 

f(n)microseconds = (1 sec * ( 10^6 microseconds) / 1 sec)

f(n) = 10^6

lg n = 10 ^6

Question: is lg an abbreviation for log base 10
or log base 2?

base 10:

log n = 10^6  ,   10^(10^6) = n

base 2:

log_2 n = 10^6,   2^(10^6) = n

[toc] | [next] | [standalone]

#5349

On 24/03/15 03:53, G G wrote:

> Question: is lg an abbreviation for log base 10
> or log base 2?
>
> base 10:
>
> log n = 10^6  ,   10^(10^6) = n
>
> base 2:
>
> log_2 n = 10^6,   2^(10^6) = n
>

lg normally means log base 10. ln normally means log base e (not 2!).

In general, if an algorithm takes (log (to the base b) n) microseconds 
to process n items and you have t microseconds available, you have time 
for processing b^t items.

So yes, your log 10 answer is correct.

All too often, in computer science, the logarithmic base that is of most 
consequence is log base 2, which doesn't even have a button on the 
calculator! Fortunately, it is easy to calculate log base 2 as follows:

#include <math.h>
double log2(double d)
{
   return log(d) / log(2.0);
}

or if you prefer:

double logb(double d, double b)
{
   return log(d) / log(b);
}

Even more fortunately, in complexity theory you very often don't care 
which logarithm base is used, because it all comes out in the wash. O(n 
log n) beats O(n^2) for any logarithmic base, for sufficiently large n.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#5352

On 2015-03-24, G G <gdotone@gmail.com> wrote:
> Question: is lg an abbreviation for log base 10
> or log base 2?

You have to clarify that with your textbook or instructor.

Though it is an ISO notation for the base 10 logarithm,
it does show up as a nonstandard notation for base 2.

I'd also be suspicious for the reason that base 10 logs don't come up that much
in the analysis of algorithm running times.  Basically that requires something
akin to a tree search that branches ten ways at each node, or otherwise reduces
an input set to 10% at each step.

[toc] | [prev] | [next] | [standalone]

#5355

Thanks, Richard and Kaz.

i'm not taking a class. i found the book at a local bookstore and read the preface. 
the author says this book makes a good self study book so i'm self studying, with 
the community's help. :-). 

and Les, at comp.lang.c, pointed me to the online offering from mit. i also found 
one on khan academy. so the author may be right, but he should have included
you guys too as a great source.  :-)   i don't know that the book is that clear cut,
but to be fair, i've just started reading it.

thanks again,
g.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web