Talk:Iterated logarithm

From Wikipedia, the free encyclopedia

Contents

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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(nlog * 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(nlog * 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)

[edit] Symmetric level-index arithmetic

Is the log*n function the same as the ψ(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)