Big O: Nested For Loop With Dependence
So let me clarify a few things, you are interested in the big-O notation - this means upper bound. In other words, it is okay to count more steps than you actually do. In particular, you can modify the algorithm to

 ...
    for (j = 0; j &lt; n; j++) 
 ...


So you have two nested loops, each loop runs $n$ times, which gives you an upper bound of $O(n^2)$

Of course, you would like to have a good estimate for the upper bound. So for completion, we want to determine a lower bound. This means its okay to count less steps. So consider the modification

for (i = n/2; i &lt; n; i++)
    for (j = 0; j &lt; n/2; j++) 
        sum++;


Here, we perform only a some of the loop-iterations. Again we have two nested loops, but this time we have $n/2$ iterations per loop, which shows that we have at least $n^2/4$ additions. In this case we denote this asymptotic lower bound by $\Omega(n^2)$. Since the lower and upper bound coincide, we can even say that $n^2$ is a tight asymptotic bound, and we write $\Theta(n^2)$.

If you want to know more, read here.