Richard Heathfield
3/24/2015 7:26:00 AM
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