请教：函数func2的时间复杂度是否为O((log(log n))²)？我的计算正确吗？

先看给出的代码：

int func2(int arr[], int n) {
    int i = 0, j, counter = 0;

    MergeSort(arr, n / 6); // 1

    while (i < n / 6) // 2
    {
        for (j = 6; j < n / 6; j *= j) // 3
            counter++;

        i = j * 6;
    }

    return counter;
}

各部分复杂度纠正： #

1. MergeSort部分：
   MergeSort的时间复杂度为O(k log k)，其中k是排序的数组长度，这里k = n/6。忽略常数系数后，复杂度为O(n log n)，这是整个函数的主导项。

2. 内层for循环：
   j从6开始，每次执行j *= j，直到j >= n/6。设循环执行次数为t，则满足6^(2^t) >= n/6。对两边取对数推导：

   • 第一次取以6为底的对数：2^t >= log₆(n/6)
   • 第二次取以2为底的对数：t >= log₂(log₆(n/6))
     忽略对数的底数（大O表示法不关注底数），内层循环的时间复杂度为O(log log n)。

3. 外层while循环：
   初始i=0，进入循环后执行完内层for循环，此时j已经满足j >= n/6，因此i = j*6 >= (n/6)*6 = n。当n足够大时，n > n/6，所以i < n/6的条件不再成立，while循环仅执行一次，复杂度为O(1)。

总时间复杂度： #

将各部分复杂度相加，主导项是MergeSort的O(n log n)，远大于后续的O(log log n)，因此总时间复杂度为O(n log n)。

你之前的错误在于误判了while循环的执行次数，同时忽略了MergeSort的复杂度是远高于嵌套循环项的主导项，所以总复杂度不可能是O((log log n)²)。

内容的提问来源于stack exchange，提问作者python_1239