Time complexity and space of the function

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

@Jean-FrançoisFabre not sure what you mean by O(2), is that a type-O? — Alejandro, Aug 14 '16 at 09:30

score 1 · Answer 1 · answered Aug 14 '16 at 09:49

A simplistic analysis gives a time complexity of O(N.log(N)), but it should be noted that the loop does not compute anything: local variable x is decremented n / i times and discarded. A good compiler should be able to compile the whole function to a no-op: void what(int n) {}, which a resulting complexity of O(1), both for space and time.

Time complexity and space of the function

1 Answers1