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

Groups > comp.programming > #5349

Re: this problem comes from chapter 1 of introduction to algorithms

Show all headers | View raw

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

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web