Ilan Aizelman WS - 1 month ago 7

C Question

Started studying about complexity, I'm struggling with this one:

`void what(int n) {`

int i;

for (i = 1; i <= n; i++) {

int x = n;

while (x > 0)

x -= i;

}

}

Well, the first for loop is clearly

`O(n)`

`O(n)`

`O(n/2)`

`log(n)`

Which means

`O(n) * O(log(n)) = O(n * log(n)) complexity`

Edit:(not a duplicate) I know what Big O is. I've asked the correct evaluation in a specific case.

Answer

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