Ilan Aizelman WS - 1 year ago 68
C Question

# What is the time complexity of my function?

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)`
. The first iteration is
`O(n)`
, second one is
`O(n/2)`
.. and like that
`log(n)`
times I guess?
Which means
`O(n) * O(log(n)) = O(n * log(n)) complexity`
. Did I get this right?

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

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