user323242342342 user323242342342 - 3 months ago 12
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

Answer

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.