0

What are the general attributes of an algorithm that cause a polylogarithmic term (e.g. O(log log N)) to be introduced into its time or space complexity?

I'm asking about general structural or behavioral properties, e.g. O(N^3) often corresponds to a triply-nested loop over all elements in a collection, or O(log N) often indicates that the algorithm could be modeled as a process of walking a path from the root to a leaf in a balanced tree.

Luke Hutchison
  • 8,186
  • 2
  • 45
  • 40
  • 1
    There is good explanation about it in this topic: https://stackoverflow.com/questions/16472012/what-would-cause-an-algorithm-to-have-olog-log-n-complexity – Naitonium Nov 07 '20 at 23:49
  • @Naitonium thank you, very helpful! I'll close the question. – Luke Hutchison Nov 08 '20 at 04:39
  • 1
    As a note, “polylogarithmic” usually means O(log^k n) = O((log n)^k) for some constant k. O(log log n) would be doubly-logarithmic rather then polylogarithmic. – templatetypedef Nov 08 '20 at 04:39
  • @templatetypedef Right, I understand. That's why I gave `O(log log N)` only as an example. But the explanation linked by @Naitonium makes the point clear -- I can extrapolate to more than two levels based on that answer. – Luke Hutchison Nov 08 '20 at 04:42
  • 1
    Oh, sorry, to clarify - (log n)^2 = (log n) * (log n) is an example of a polylogarithmic runtime. That is, polylogarithmic runtimes usually refer to runtimes made by multiplying logarithms together. On the other hand, log log n = log (log n) is typically not considered polylogarithmic, since it involves composing logarithms together rather than multiplying them. – templatetypedef Nov 08 '20 at 06:31

0 Answers0