Talk:Iterated logarithm

Iterated log vs Ackermann

"The disjoint set data structure's union and find operations" is given as an example algorithm using iterated log complexity, but Disjoint_set_data_structure mentions the (better) inverse Ackermann bound. -- hagman --195.227.74.194 10:11, 15 November 2006 (UTC)

Yes, there's an old version that has iterated log complexity. I can't recall its name off the top of my head. CRGreathouse (t | c) 17:44, 15 November 2006 (UTC)

Vs. "Law of"

Do Iterated logarithm and Law of the iterated logarithm have something in common despite the name? --Abdull 13:31, 3 March 2006 (UTC)

• No; the law uses 2 logs exactly; this uses as many as necessary to get below 1, and counts them. Septentrionalis PMAnderson 06:09, 13 January 2008 (UTC)

Figure 1

It would be nice if Figure 1 illustrated the line segments shown with arrowheads 12.208.40.109 16:53, 30 May 2006 (UTC)

I have corrected the caption on this diagram. The values on the y axis reveal that the graph is showing the natural logarithm of x, and thus calculating log^*x, while the caption claimed to be calculating lg^*x. It's still confusing, since the diagram is only referred to during the discussion of lg^*x, but I think that's a lot better than having a clearly erroneous caption. --Weeble (talk) 15:40, 26 November 2007 (UTC)

I can fix this. Dcoetzee 23:52, 26 November 2007 (UTC)

Reference?

I haven't finished reading it yet, but there's a mention of the iterated logarithm in Sublogarithmic Ambiguity that may be of use in the article. CRGreathouse (t | c) 07:19, 26 September 2006 (UTC)

Another: Dr. Jamie Andrews suggests the possibility of an $O(n^{\log *n})$ algorithm for an NP-complete problem (rendiring P =? NP moot). [1] CRGreathouse (t | c) 05:10, 28 September 2006 (UTC)

I read that paper, and the $O(n^{\log *n})$ bit was a joke. I don't mean "a joke" in the sense of "not adequately demonstrated" but rather "accompanied by a smiley and meant to be amusing." 74.74.206.149 (talk) 13:25, 6 February 2008 (UTC)

Agreed, it was just making a point. CRGreathouse (t | c) 18:45, 6 February 2008 (UTC)

Another: [2] CRGreathouse (t | c) 02:35, 14 August 2010 (UTC)

Symmetric level-index arithmetic

Is the log^*n function the same as the ${\psi (X)}$ function described in Symmetric level-index arithmetic? Do the different names for the function (generalized logarithm vs. iterated logarithm) just come from the fact that they arose in different branches of math? --Rpresser 22:04, 10 March 2008 (UTC)

They're almost the same: $\log ^{*}x=\lfloor \psi (x)\rfloor$, provided x ≥ 0. CRGreathouse (t | c) 22:57, 10 March 2008 (UTC)

HTML log-star

See Talk:Time complexity#HTML log-star for a discussion regarding how to write log* in Wikipedia. As a result of the discussion, I created the simple templates {{log-star}} and {{lg-star}} and edited this article as well. — Miym (talk) 21:20, 15 January 2010 (UTC)

log* n

Should be redirected here. —Preceding unsigned comment added by 193.126.183.46 (talk) 15:30, 22 June 2010 (UTC)

But why? Does any article link to it? In any case, done. log* already redirected here since a long time ago. Shreevatsa (talk) 16:04, 22 June 2010 (UTC)

Explanation of "well-defined" statement

Quoting from the lead:

Mathematically, the iterated logarithm is well-defined not only for base 2 and base e, but for any base greater than $e^{1/e}\approx 1.444667$.

I'm a little rusty right now, so i couldn't readily explain to myself why would lower values not generate a sequence {$x_{0}=0,x_{n+1}=b^{x_{n}}$} that grows up to infinity... It's obviously monotonically increasing, but i just don't see the reason why it would have a finite bound. Can anyone provide a hint? -- Jokes Free4Me (talk) 17:12, 12 July 2013 (UTC)

Complexity of Fürer's algorithm

I think the complexity of Fürer's algorithm is $n\log n\,2^{O(\log ^{*}n)}$ (see Fürer's_algorithm), and not, as mentioned here, O(n log n 2^lg* n). These bounds are different, because there is a "better" algorithm with complexity $O(n\log n\,2^{3\log ^{*}n})$ (see also Fürer's_algorithm), which is even worse than O(n log n 2^lg* n). So I think this must be corrected here.

Yes, changing expressions of the form a^O(b) to O(a^b) is a frequent mistake. I've fixed this one. Thanks for catching it. —David Eppstein (talk) 18:40, 21 December 2014 (UTC)

Iterative function as well as recursive?

The mathematical definition given is recursive. The very term has the word 'iterated' in it, and the iterative version is indeed simpler to understand. Should we give that as well? Here's some pseudo code of the function:

int iteratedLog (float n, float b) {

    count = 0;

    while (n >= 1.0) {

        n = LogBase b (n);

        count = count+1;

    }

    return count;

}

--Skytopia (talk) 11:57, 10 May 2015 (UTC)