以下递归函数的时间复杂度

Question

下面递归函数的时间复杂度是多少

int DoSomething(int n){
     if(n<=2) 
        return 1;
     else 
        return (DoSomething(floor(sqrt( n) )) + n);
}

选项是：-

1. O(n^2)
2. O(n log n) //所有日志都以 2 为底
3. O(log n )
4. O(log log n )

Answer 1

时间复杂度函数为（忽略floor，因为它渐近无关）：

我们需要在算法终止时找到 m，即当：