,,improve'' readability in tree(3)

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

,,improve'' readability in tree(3)

Thordur I. Bjornsson
lg -> log


Index: tree.3
===================================================================
RCS file: /cvs/src/share/man/man3/tree.3,v
retrieving revision 1.12
diff -u -p -r1.12 tree.3
--- tree.3 2005/04/16 06:11:35 1.12
+++ tree.3 2006/03/08 21:34:44
@@ -173,8 +173,8 @@ the requested nodes move to the top of t
 On the other hand, every lookup causes memory writes.
 .Pp
 The Balance Theorem bounds the total access time for m operations
-and n inserts on an initially empty tree as O((m + n)lg n).
-The amortized cost for a sequence of m accesses to a splay tree is O(lg n).
+and n inserts on an initially empty tree as O((m + n)log n).
+The amortized cost for a sequence of m accesses to a splay tree is O(log n).
 .Pp
 A splay tree is headed by a structure defined by the
 .Fn SPLAY_HEAD
@@ -302,8 +302,8 @@ each red node (except for the root) has
 each leaf node is black.
 .El
 .Pp
-Every operation on a red-black tree is bounded as O(lg n).
-The maximum height of a red-black tree is 2lg (n+1).
+Every operation on a red-black tree is bounded as O(log n).
+The maximum height of a red-black tree is 2log(n+1).
 .Pp
 A red-black tree is headed by a structure defined by the
 .Fn RB_HEAD

 --
Thordur I. Bjornsson
Humppa!

Reply | Threaded
Open this post in threaded view
|

Re: ,,improve'' readability in tree(3)

Peter Valchev
> lg -> log

No, the original is correct.  lg means log base 2.


> Index: tree.3
> ===================================================================
> RCS file: /cvs/src/share/man/man3/tree.3,v
> retrieving revision 1.12
> diff -u -p -r1.12 tree.3
> --- tree.3 2005/04/16 06:11:35 1.12
> +++ tree.3 2006/03/08 21:34:44
> @@ -173,8 +173,8 @@ the requested nodes move to the top of t
>  On the other hand, every lookup causes memory writes.
>  .Pp
>  The Balance Theorem bounds the total access time for m operations
> -and n inserts on an initially empty tree as O((m + n)lg n).
> -The amortized cost for a sequence of m accesses to a splay tree is O(lg n).
> +and n inserts on an initially empty tree as O((m + n)log n).
> +The amortized cost for a sequence of m accesses to a splay tree is O(log n).
>  .Pp
>  A splay tree is headed by a structure defined by the
>  .Fn SPLAY_HEAD
> @@ -302,8 +302,8 @@ each red node (except for the root) has
>  each leaf node is black.
>  .El
>  .Pp
> -Every operation on a red-black tree is bounded as O(lg n).
> -The maximum height of a red-black tree is 2lg (n+1).
> +Every operation on a red-black tree is bounded as O(log n).
> +The maximum height of a red-black tree is 2log(n+1).
>  .Pp
>  A red-black tree is headed by a structure defined by the
>  .Fn RB_HEAD
>
>  --
> Thordur I. Bjornsson
> Humppa!

Reply | Threaded
Open this post in threaded view
|

Re: ,,improve'' readability in tree(3)

Kjell-5
> > lg -> log
>
> No, the original is correct.  lg means log base 2.

Technically, it's half right, since the constant which differentiates
(lg n) from (log n) is eaten by the big-O.

But I'll go back under my rock now.

> > -Every operation on a red-black tree is bounded as O(lg n).
> > -The maximum height of a red-black tree is 2lg (n+1).
> > +Every operation on a red-black tree is bounded as O(log n).
> > +The maximum height of a red-black tree is 2log(n+1).
> >  .Pp
> >  A red-black tree is headed by a structure defined by the
> >  .Fn RB_HEAD

-kj

Reply | Threaded
Open this post in threaded view
|

Re: ,,improve'' readability in tree(3)

Thorsten Glaser-3
In reply to this post by Peter Valchev
Peter Valchev dixit:

>> lg -> log
>
>No, the original is correct.  lg means log base 2.

Isn't that lb?

//mirabile
--
I believe no one can invent an algorithm. One just happens to hit upon it
when God enlightens him. Or only God invents algorithms, we merely copy them.
If you don't believe in God, just consider God as Nature if you won't deny
existence. -- Coywolf Qi Hunt

Reply | Threaded
Open this post in threaded view
|

Re: ,,improve'' readability in tree(3)

Jon Simola-2
On 3/8/06, Thorsten Glaser <[hidden email]> wrote:

> >No, the original is correct.  lg means log base 2.
>
> Isn't that lb?

Quoting wikipedia:

"In computer science, the base 2 logarithm is sometimes written as
lg(x) to avoid confusion. This usage was suggested by Edward Reingold
and popularized by Donald Knuth."

--
Jon Simola
Systems Administrator
ABC Communications

Reply | Threaded
Open this post in threaded view
|

Re: ,,improve'' readability in tree(3)

Thordur I. Bjornsson
In reply to this post by Thorsten Glaser-3
Thorsten Glaser <[hidden email]> wrote on Wed  8.Mar'06 at 22:33:03 +0000

> Peter Valchev dixit:
>
> >> lg -> log
> >
> >No, the original is correct.  lg means log base 2.
>
> Isn't that lb?
>
I was under that expression (log base 2 -> lb) never seen
,,lg'' before.

And (no that I generally trust wikipedia) you see for example
that:

'' Balance Theorem: The cost of performing the sequence S is O(m(logn + 1) + nlogn).
In other words, splay trees perform as well as static balanced
binary search trees on sequences of at least n accesses. ''

-> http://en.wikipedia.org/wiki/Splay_tree

--
Thordur I. Bjornsson
Humppa!

Reply | Threaded
Open this post in threaded view
|

Re: ,,improve'' readability in tree(3)

Ilya A. Kovalenko
In reply to this post by Jon Simola-2
>> >No, the original is correct.  lg means log base 2.
>>
>> Isn't that lb?

JS> Quoting wikipedia:

JS> "In computer science, the base 2 logarithm is sometimes written as
JS> lg(x) to avoid confusion. This usage was suggested by Edward Reingold
JS> and popularized by Donald Knuth."

  There is no out-of-context-unambiguous short notation for log10 and log2
(from the very Wikipedia article). Best, IMHO, is to make notation notes
inside article or use full notation i.e. log<sub>2/10</sub> or just
log2/10.

  For example, I've always thinking that "lg" means "log<sub>10</sub>" (as was
taught on high school).

Reply | Threaded
Open this post in threaded view
|

Re: ,,improve'' readability in tree(3)

Marc Espie-2
- it doesn't matter for O() notation.
- whatever your log is, just write log(val)/log 2 there.
That can't be ambiguous... ;-)