Nested for loop in Big Oh Complexity

Question

for(int i = 0; i < n; i++) {
    for(int j = 0; j < i; j++){
        // do swap stuff, constant time
    }
}

I read that single for loop is O(N) and traversing it twice will make it O(n^2).

I watched related tutorials which shows that each operation takes unit of 1 - O(1). I would like see in details how O(n^2) actually came up. I tried to do math for each statement but I believe I am not doing it right. I would appreciate if someone can literally show me how nested for loop becomes O(n^2). Thanks beforehand

Answer 1

You need to use the ancient and obscure art of mathematics and calculate the number of times that the inner statement is executed.

In your case, the inner loop is executed i times. The values for i are 0, 1, 2, ..., n-1. So you need a formula that calculates this sum, and that's your result.

You read that a single loop is O (n). That's nonsense. It depends on the loop.

for (i = 1; i < n; i *= n)

doesn't iterate n times. It iterates log2 (n) times, which is usually an awful lot less. You need to look at the actual code and figure it out. There is no simple rule for this.