bounds - 寻找大 theta 界

Question

给定大 theta：

for (int i = 0; i < n; i++) {
    if (i * i < n) {
         for (int j = 0; j < n; j++) {
             count++;
         }
    }
    else {
        int k = i;
        while (k > 0) {
            count++;
            k = k / 2;
        }
    }
}

所以这就是我的想法..不确定是否正确：

第一个 for 循环将运行 n 次迭代。然后第一个 for 循环中的 for for 循环也将运行 n 次迭代，给出 O(n^2)。

对于 else 语句，while 循环将运行 n 次迭代，而 k = k/ 2 将运行 logn 时间，给出 O(nlogn)。那么整个事情看起来像 n^2 + nlogn 并且通过更长的运行时间，答案将是 theta n^2 ？

Answer 1

我会说结果是O(nlogn)因为i*i对于线性 n 通常不小于 n。else 分支将占主导地位。

例子：

n= 10000
after i=100 the else part will be calculated instead of the inner for loop