C语言 需要计算代码复杂度的帮助

Question

我有一个小代码，我需要知道的复杂性和不能弄清楚它自己，有人可以帮助/指导我的解决方案?

int funn(int n) {
    int i, j, k = 0;
    for (i = n / 2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n / 2;
    return k;
}

一开始，我认为复杂度是O(n)，但有一些乘法我不确定。我是新手，所以我需要一个指导

Answer 1

外循环为(n/2)，即O(n)。内环是O(log n)

所以整个是O(n log n)