Meaning of lg * N in Algorithmic Analysis

algorithm runtime big-o analysis iterated-logarithm
themaestro picture themaestro · Mar 6, 2011 · Viewed 17k times · Source

I'm currently reading about algorithmic analysis and I read that a certain algorithm (weighted quick union with path compression) is of order N + M lg * N. Apparently though this is linear because lg * N is a constant in this universe. What mathematical operation is being referred to here. I am unfamiliar with the notation lg * N.

Answer

jason picture jason · Mar 6, 2011

The answers given here so far are wrong. lg* n (read "log star") is the iterated logarithm. It is defined as recursively as

         0             if n <= 1
lg* n =
         1 + lg*(lg n) if n > 1

Another way to think of it is the number of times that you have to iterate logarithm before the result is less than or equal to 1.

It grows extremely slowly. You can read more on Wikipedia which includes some examples of algorithms for which lg* n pops up in the analysis.

Related questions

The Best Search Algorithm for a Linked List

I have to write a program as efficiently as possible that will insert given nodes into a sorted LinkedList. I'm thinking of how binary search is faster than linear in average and worst case, but when I Googled it, the …

Read More
How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More
Removing duplicates in the lists

Pretty much I need to write a program that checks if a list has any duplicates and if it does it removes them and returns a new list with the items that weren't duplicated/removed. This is what I have …

Read More