user323242342342 - 2 months ago 5x

C Question

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.

Source (Stackoverflow)

Comments