user323242342342 - 1 year ago 81
C Question

# Time complexity and space of the function

im sturggling with finding complexity of the next function

``````void what(int n) {
int i;
for (i = 1; i <= n; i++) {
int x = n;
while (x > 0)
x -= i;
}
}
``````

ive tried to solve it by the next things
at looking on space i found its only O(1) since no taking of it.
when thinking of time
i thought that since its each time being devided it will be n(1+1/2 +1/4+....)=O(N.log(N))
is it correct?
thank you

Space comlexity is O(1) as mentioned The outer loop runs `n` times.

For each iteration, the inner loops runs `n / i` times.

The total number of runs is

``````n + n/2 + n/3 + ... + n/n
``````

Asymptotically (ignoring integer arithmetic rounding), this simplifies as

``````n (1 + 1/2 + 1/3 + ... + 1/n)
``````

This series loosely converges towards `n * log(n)`.

Hence the complexity is `O(N.log(N))` as you expected.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download