0

I have been browsing youtube and wikipedia but couldn't find anything related to algorithm's runtime, can someone explain to me what does it mean if an algorithm has a run time of O(log*(n))?

Pig
  • 2,002
  • 5
  • 26
  • 42
  • 1
    When you [google 'algorithm runtime'](http://i.imgur.com/sGIDUM9.png), the first result gives a wiki page for background info, the second a big-o cheatsheet for many datastructures and the third [this exact question on CS.se](http://cs.stackexchange.com/questions/192/how-to-come-up-with-the-runtime-of-algorithms). Likewise, when you google "O(log*(n))", you get [this answer](http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly). Please, make an effort. – Jeroen Vannevel Mar 09 '14 at 00:47
  • @Jeroen: Actually `log*(n)` is something entirely different from `log(n)`, and it's hard to Google as well, for obvious reasons. Since OP does know the actual name (iterated logarithm), it's easier, but it's still hard to find a plain English explanation of when this is relevant – Niklas B. Mar 09 '14 at 02:05
  • @NiklasB. The plain English explanation webpage does not have log*(n) though.. – Pig Mar 09 '14 at 02:16
  • I don't see how this is a duplicate. There is no mention of iterated logarithm on that question or its answers. – Niklas B. Mar 09 '14 at 04:44
  • It helps to search for "log-star", then one may find https://en.wikipedia.org/wiki/Log-star, and also http://stackoverflow.com/questions/5212628/meaning-of-lg-n-in-algorithmic-analysis, http://stackoverflow.com/questions/21948272/finding-big-theta. According to these sources, `log*(n)` means the minimum `p` such that `log^p(n)=log(log(...(n)...))<1`. – Lutz Lehmann Mar 09 '14 at 16:40

0 Answers0