[Solved] Is there a way to do the sum of the n integers function that would have O(n^2)?

Question

I’m not really sure why you want this, but you could do it with two nested loops:

int getSum(int n) {
    int sum = 0;
    for(int i = 1; i <= n; i++) {
        int x = 0;
        while(x++ < i) {
            sum++;
        }
    }
    return sum;
}

This runs 1+2+3+...+n times, which simplifies to (n^2+n)/2, hence O(n^2)

Accepted Answer

I’m not really sure why you want this, but you could do it with two nested loops:

int getSum(int n) {
    int sum = 0;
    for(int i = 1; i <= n; i++) {
        int x = 0;
        while(x++ < i) {
            sum++;
        }
    }
    return sum;
}

This runs 1+2+3+...+n times, which simplifies to (n^2+n)/2, hence O(n^2)