相关疑难解决方法(0)

我这里有一个简短的程序:

Given any n:
i = 0;
while (i < n) {
   k = 2;
   while (k < n) {
        sum += a[j] * b[k]
        k = k * k;
   }
   i++;
}

这个的渐近运行时间是O(n log log n).为什么会这样？我知道整个程序至少会运行n次.但我不知道如何找到日志日志n.内循环取决于k*k,所以它显然小于n.如果每次都是k/2那么它就是n log n.但是你怎么能找到答案是log log n？