703:
276:
574:
150:
767:
569:
The iterated logarithm grows at an extremely slow rate, much slower than the logarithm itself, or repeats of it. This is because the tetration grows much faster than iterated exponential:
27:
359:
1201:
1004:
430:
1163:
931:
1355:
1192:
450:
379:
314:
138:
106:
79:
780: ≤ 2, which is far more than the estimated number of atoms in the known universe), the iterated logarithm with base 2 has a value no more than 5.
37:(x) from the input n, to the interval . In this case, b = e. The zig-zagging entails starting from the point (n, 0) and iteratively moving to (n, log
33:
Demonstrating log* 4 = 2 for the base-e iterated logarithm. The value of the iterated logarithm can be found by "zig-zagging" on the curve y = log
1258:
698:{\displaystyle {^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}\gg \underbrace {b^{b^{\cdot ^{\cdot ^{b^{y}}}}}} _{n}}
271:{\displaystyle \log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}}
1362:
710:
1384:
1061:
1364:
Proceedings of the 16th Annual IEEE Conference on
Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001
960:
880:
543:
1309:
937:
485:
473:
876:
323:
20:
966:
388:
1406:
1123:
1051:
1266:
1119:
1050:(2009) . "The iterated logarithm function, in Section 3.2: Standard notations and common functions".
178:
894:
887:, the number of times someone must replace the number by the sum of its digits before reaching its
1317:
884:
1168:
510:
1014:
941:
481:
469:
1368:
1340:
1287:
1232:
1104:
1039:
8:
1411:
141:
1236:
1210:
435:
364:
299:
123:
91:
64:
1331:
1380:
1057:
776:
relevant to counting the running times of algorithms implemented in practice (i.e.,
320:). Mathematically, the iterated logarithm is well defined for any base greater than
1372:
1326:
1275:
1220:
1090:
1035:
1017:, an even more slowly growing function also used in computational complexity theory
293:
54:
1336:
1301:
1283:
1240:
1228:
1100:
948:
476:, appearing in the time and space complexity bounds of some algorithms such as:
1310:"Deterministic coin tossing with applications to optimal parallel list ranking"
1047:
952:
489:
1224:
1400:
1376:
888:
524:
Finding an approximate maximum (element at least as large as the median):
1305:
539:
1043:
1095:
1078:
1254:
457:
117:
113:
26:
1279:
1215:
453:
1202:
International
Journal of Computational Geometry & Applications
956:
944:
1056:(3rd ed.). MIT Press and McGraw-Hill. pp. 58–59.
452:
iterated logarithm (although differing in minor details of
264:
1034:
140:. The simplest formal definition is the result of this
246:
187:
1171:
1126:
969:
897:
713:
577:
438:
391:
367:
326:
302:
153:
126:
94:
67:
120:applied before the result is less than or equal to
1356:"On separators, segregators and time versus space"
1186:
1157:
998:
925:
761:
697:
444:
424:
373:
353:
308:
270:
132:
100:
73:
875:The iterated logarithm is closely related to the
1398:
762:{\displaystyle \log _{b}^{*}x\ll \log _{b}^{n}x}
867:Higher bases give smaller iterated logarithms.
316:) instead of the natural logarithm (with base
1300:
456:) and forms an inverse to the operation of
19:For the theorem in probability theory, see
1076:
1353:
1330:
1214:
1117:
1094:
463:
1253:
544:distributed algorithm for 3-coloring an
432:is "essentially equivalent" to the base
25:
354:{\displaystyle e^{1/e}\approx 1.444667}
1399:
999:{\displaystyle n{\sqrt {\log ^{*}n}}.}
425:{\displaystyle \mathrm {slog} _{b}(n)}
870:
16:Inverse function to a tower of powers
1077:Furuya, Isamu; Kida, Takuya (2019).
468:The iterated logarithm is useful in
565:) synchronous communication rounds.
13:
1172:
1158:{\displaystyle O(n\log ^{\ast }n)}
403:
400:
397:
394:
14:
1423:
1118:Devillers, Olivier (March 1992).
385:. The "super-logarithm" function
1259:"Finding an approximate maximum"
961:non-deterministic Turing machine
881:symmetric level-index arithmetic
1079:"Compaction of Church numerals"
938:computational complexity theory
707:the inverse grows much slower:
486:Euclidean minimum spanning tree
484:of a set of points knowing the
112:"), is the number of times the
1347:
1294:
1247:
1181:
1175:
1152:
1130:
1111:
1070:
1028:
920:
901:
877:generalized logarithm function
784:The base-2 iterated logarithm
513:for integer multiplication: O(
419:
413:
288:is often used to indicate the
240:
228:
1:
1332:10.1016/S0019-9958(86)80023-7
1120:"Randomization yields simple
1021:
926:{\displaystyle O(\log ^{*}n)}
21:Law of the iterated logarithm
1257:; Azar, Yossi (April 1989).
953:deterministic Turing machine
535:− 1 ± 3 parallel operations.
7:
1008:
940:, Santhanam shows that the
10:
1428:
1187:{\displaystyle \Omega (n)}
1053:Introduction to Algorithms
1015:Inverse Ackermann function
18:
1354:Santhanam, Rahul (2001).
1267:SIAM Journal on Computing
1225:10.1142/S021819599200007X
1165:algorithms for difficult
959:— computation time for a
290:binary iterated logarithm
474:computational complexity
1377:10.1109/CCC.2001.933895
1318:Information and Control
942:computational resources
885:persistence of a number
1188:
1159:
1000:
927:
763:
699:
482:Delaunay triangulation
470:analysis of algorithms
464:Analysis of algorithms
446:
426:
375:
355:
310:
272:
134:
102:
75:
50:
1369:IEEE Computer Society
1189:
1160:
1040:Leiserson, Charles E.
1001:
963:— are distinct up to
928:
764:
700:
447:
427:
376:
356:
311:
292:, which iterates the
281:In computer science,
273:
135:
103:
76:
29:
1371:. pp. 286–294.
1169:
1124:
967:
895:
711:
575:
436:
389:
365:
361:, not only for base
324:
300:
151:
124:
92:
65:
1407:Asymptotic analysis
785:
752:
728:
142:recurrence relation
1184:
1155:
996:
923:
871:Other applications
783:
772:For all values of
759:
738:
714:
695:
694:
687:
639:
632:
442:
422:
371:
351:
306:
268:
263:
250:
191:
130:
116:function must be
98:
71:
59:iterated logarithm
51:
1096:10.3390/a12080159
1044:Rivest, Ronald L.
1036:Cormen, Thomas H.
991:
865:
864:
645:
643:
597:
595:
538:Richard Cole and
511:Fürer's algorithm
445:{\displaystyle b}
374:{\displaystyle 2}
309:{\displaystyle 2}
249:
190:
133:{\displaystyle 1}
101:{\displaystyle n}
74:{\displaystyle n}
41:(n) ), to (0, log
1419:
1391:
1390:
1360:
1351:
1345:
1344:
1334:
1314:
1298:
1292:
1291:
1263:
1251:
1245:
1244:
1218:
1198:
1193:
1191:
1190:
1185:
1164:
1162:
1161:
1156:
1145:
1144:
1115:
1109:
1108:
1098:
1074:
1068:
1067:
1032:
1005:
1003:
1002:
997:
992:
984:
983:
974:
949:computation time
932:
930:
929:
924:
913:
912:
858:
848:
838:
828:
818:
808:
797:
786:
782:
768:
766:
765:
760:
751:
746:
727:
722:
704:
702:
701:
696:
693:
688:
683:
682:
681:
680:
679:
678:
677:
676:
675:
674:
638:
633:
628:
627:
626:
625:
624:
623:
622:
621:
591:
587:
586:
559:
529:
501:
451:
449:
448:
443:
431:
429:
428:
423:
412:
411:
406:
380:
378:
377:
372:
360:
358:
357:
352:
344:
343:
339:
315:
313:
312:
307:
294:binary logarithm
286:
277:
275:
274:
269:
267:
266:
251:
247:
224:
223:
192:
188:
163:
162:
139:
137:
136:
131:
107:
105:
104:
99:
86:
80:
78:
77:
72:
55:computer science
1427:
1426:
1422:
1421:
1420:
1418:
1417:
1416:
1397:
1396:
1395:
1394:
1387:
1358:
1352:
1348:
1312:
1299:
1295:
1280:10.1137/0218017
1261:
1252:
1248:
1196:
1170:
1167:
1166:
1140:
1136:
1125:
1122:
1121:
1116:
1112:
1075:
1071:
1064:
1048:Stein, Clifford
1033:
1029:
1024:
1011:
979:
975:
973:
968:
965:
964:
908:
904:
896:
893:
892:
883:. The additive
873:
856:
847:(16, 65536]
846:
836:
826:
816:
806:
795:
747:
742:
723:
718:
712:
709:
708:
689:
670:
666:
665:
661:
660:
656:
655:
651:
650:
646:
644:
634:
617:
613:
612:
608:
607:
603:
602:
598:
596:
582:
579:
578:
576:
573:
572:
557:
527:
517: log
499:
466:
437:
434:
433:
407:
393:
392:
390:
387:
386:
366:
363:
362:
335:
331:
327:
325:
322:
321:
301:
298:
297:
284:
262:
261:
245:
243:
219:
215:
206:
205:
186:
184:
174:
173:
158:
154:
152:
149:
148:
125:
122:
121:
108:(usually read "
93:
90:
89:
84:
66:
63:
62:
48:
44:
40:
36:
24:
17:
12:
11:
5:
1425:
1415:
1414:
1409:
1393:
1392:
1385:
1346:
1293:
1274:(2): 258–267.
1246:
1183:
1180:
1177:
1174:
1154:
1151:
1148:
1143:
1139:
1135:
1132:
1129:
1110:
1089:(8) 159: 159.
1069:
1062:
1026:
1025:
1023:
1020:
1019:
1018:
1010:
1007:
995:
990:
987:
982:
978:
972:
922:
919:
916:
911:
907:
903:
900:
872:
869:
863:
862:
859:
857:(65536, 2]
853:
852:
849:
843:
842:
839:
833:
832:
829:
823:
822:
819:
813:
812:
809:
803:
802:
792:
758:
755:
750:
745:
741:
737:
734:
731:
726:
721:
717:
692:
686:
673:
669:
664:
659:
654:
649:
642:
637:
631:
620:
616:
611:
606:
601:
594:
590:
585:
581:
567:
566:
536:
522:
508:
465:
462:
441:
421:
418:
415:
410:
405:
402:
399:
396:
370:
350:
347:
342:
338:
334:
330:
305:
279:
278:
265:
260:
257:
254:
244:
242:
239:
236:
233:
230:
227:
222:
218:
214:
211:
208:
207:
204:
201:
198:
195:
185:
183:
180:
179:
177:
172:
169:
166:
161:
157:
129:
97:
70:
46:
45:(n) ), to (log
42:
38:
34:
15:
9:
6:
4:
3:
2:
1424:
1413:
1410:
1408:
1405:
1404:
1402:
1388:
1386:0-7695-1053-1
1382:
1378:
1374:
1370:
1366:
1365:
1357:
1350:
1342:
1338:
1333:
1328:
1324:
1320:
1319:
1311:
1308:(July 1986).
1307:
1303:
1302:Cole, Richard
1297:
1289:
1285:
1281:
1277:
1273:
1269:
1268:
1260:
1256:
1250:
1242:
1238:
1234:
1230:
1226:
1222:
1217:
1212:
1209:(1): 97–111.
1208:
1204:
1203:
1195:
1178:
1149:
1146:
1141:
1137:
1133:
1127:
1114:
1106:
1102:
1097:
1092:
1088:
1084:
1080:
1073:
1065:
1063:0-262-03384-4
1059:
1055:
1054:
1049:
1045:
1041:
1037:
1031:
1027:
1016:
1013:
1012:
1006:
993:
988:
985:
980:
976:
970:
962:
958:
954:
950:
946:
943:
939:
934:
917:
914:
909:
905:
898:
890:
886:
882:
878:
868:
860:
855:
854:
850:
845:
844:
840:
835:
834:
830:
825:
824:
820:
815:
814:
810:
805:
804:
801:
793:
791:
788:
787:
781:
779:
775:
770:
756:
753:
748:
743:
739:
735:
732:
729:
724:
719:
715:
705:
690:
684:
671:
667:
662:
657:
652:
647:
640:
635:
629:
618:
614:
609:
604:
599:
592:
588:
583:
580:
570:
564:
560:
553:
549:
547:
541:
537:
534:
530:
523:
520:
516:
512:
509:
506:
502:
495:
491:
488:: randomized
487:
483:
479:
478:
477:
475:
471:
461:
459:
455:
439:
416:
408:
384:
368:
348:
345:
340:
336:
332:
328:
319:
303:
295:
291:
287:
258:
255:
252:
237:
234:
231:
225:
220:
216:
212:
209:
202:
199:
196:
193:
181:
175:
170:
167:
164:
159:
155:
147:
146:
145:
143:
127:
119:
115:
111:
95:
87:
68:
60:
56:
32:
28:
22:
1363:
1349:
1325:(1): 32–53.
1322:
1316:
1306:Vishkin, Uzi
1296:
1271:
1265:
1249:
1206:
1200:
1113:
1086:
1082:
1072:
1052:
1030:
935:
889:digital root
874:
866:
799:
789:
777:
773:
771:
706:
571:
568:
562:
555:
551:
545:
532:
525:
518:
514:
504:
497:
493:
480:Finding the
467:
382:
317:
289:
282:
280:
109:
82:
58:
52:
30:
837:(4, 16]
807:(−∞, 1]
540:Uzi Vishkin
296:(with base
118:iteratively
1412:Logarithms
1401:Categories
1255:Alon, Noga
1216:cs/9810007
1083:Algorithms
1022:References
827:(2, 4]
817:(1, 2]
81:, written
1194:problems"
1173:Ω
1147:
1142:∗
986:
981:∗
915:
910:∗
754:
736:≪
730:
725:∗
685:⏟
663:⋅
658:⋅
641:≫
630:⏟
615:⋅
610:⋅
521: 2).
458:tetration
381:and base
346:≈
235:
226:
221:∗
197:≤
165:
160:∗
114:logarithm
49:(n), 0 ).
31:Figure 1.
1009:See also
879:used in
454:rounding
349:1.444667
248:if
189:if
110:log star
1341:0853994
1288:0986665
1233:1159844
1105:3998658
507:) time.
1383:
1339:
1286:
1239:
1231:
1103:
1060:
955:— and
951:for a
798:
561:
548:-cycle
531:
503:
496:
88:
57:, the
1359:(PDF)
1313:(PDF)
1262:(PDF)
1241:60203
1237:S2CID
1211:arXiv
1197:(PDF)
957:NTIME
945:DTIME
891:, is
1381:ISBN
1058:ISBN
472:and
256:>
1373:doi
1327:doi
1276:doi
1221:doi
1138:log
1091:doi
977:log
936:In
906:log
740:log
716:log
556:log
542:'s
498:log
232:log
217:log
156:log
83:log
61:of
53:In
1403::
1379:.
1367:.
1361:.
1337:MR
1335:.
1323:70
1321:.
1315:.
1304:;
1284:MR
1282:.
1272:18
1270:.
1264:.
1235:.
1229:MR
1227:.
1219:.
1205:.
1199:.
1101:MR
1099:.
1087:12
1085:.
1081:.
1046:;
1042:;
1038:;
947:—
933:.
861:5
851:4
841:3
831:2
821:1
811:0
794:lg
769:.
550::
526:lg
460:.
283:lg
171::=
144::
1389:.
1375::
1343:.
1329::
1290:.
1278::
1243:.
1223::
1213::
1207:2
1182:)
1179:n
1176:(
1153:)
1150:n
1134:n
1131:(
1128:O
1107:.
1093::
1066:.
994:.
989:n
971:n
921:)
918:n
902:(
899:O
800:x
796:*
790:x
778:n
774:n
757:x
749:n
744:b
733:x
720:b
691:n
672:y
668:b
653:b
648:b
636:y
619:b
605:b
600:b
593:=
589:b
584:y
563:n
558:*
554:(
552:O
546:n
533:n
528:*
519:n
515:n
505:n
500:*
494:n
492:(
490:O
440:b
420:)
417:n
414:(
409:b
404:g
401:o
398:l
395:s
383:e
369:2
341:e
337:/
333:1
329:e
318:e
304:2
285:*
259:1
253:n
241:)
238:n
229:(
213:+
210:1
203:;
200:1
194:n
182:0
176:{
168:n
128:1
96:n
85:*
69:n
47:b
43:b
39:b
35:b
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
