迭代对数的大theta

Question

我有两个数学函数：log（log * n）和2 ^（log * n）。现在，我想计算这两个函数的渐近增长（尤其是我想找到大theta）。最后，我想比较一下它们的复杂性。任何人都可以分享可以解决此类问题的正式/直观的解决方案吗？

谢谢。

Answer 1

这很有趣。让我们从使用标准技术开始：很难对指数进行推理，因此让我们取其对数来看看会发生什么。剩下的就是这些功能：

log（log（log * n））和log * n。

现在的问题是，他们如何相互比较。一般来说，某些功能的日志增长速度总是比功能本身慢，但前提是该功能随着功能的增长而不断增长。使用对所有k≥1的log k 2 ^{2 2 2] [] >>>，我们将得到log * n≥ 4，因此log log * n≥2，因此log log log * n≤log * n，这使我们得出log log log * n = O（log * n）。从那里开始，不难证明log log * n = O（2 log * n）。}