If I have a function that evaluates every pair of elements in a list, including pairs of an element with itself and with elements it has previously been evaluated against, the complexity of that function is, obviously, $O(n^2)$:
for (let i=0; i < n; i++) {
for (let j=0; j < n; j++) {
// this line will be executed n * n times
operate(l[i], l[j]);
}
}
However, if I have a variant of that loop that only considers pairs of elements that have not yet been compared, is the complexity of that function still $O(n^2)$?
for (let i=0; i < n; i++) {
for (let j=i+1; j < n; j++) {
// this line will be executed (n * n-1) / 2 times?
operate(l[i], l[j]);
}
}
There are a few things about this that I still don't understand:
- How can we calculate that the furthering reduction in
jwill divide the operations by 2? (I'm only inferring the $/2$ because I know that matchup tables have half the table redundant; I wouldn't know how to evaluate the reduction if, say, only even indices were compared against odd indices.) - Why doesn't that $/2$ matter? How do we determine the asymptote? How does $(n * (n-1)) / 2$ get reduced to $O(n^2)$? Are we just removing terms in reverse order of operations, by picking which one incorporates higher-order operations on variables (so $(n * (n-1)) / 2$ becomes $(n * (n-1))$, which becomes $(n * n)$)?
- How does this generalize for $x$-tuples? If we're comparing triplets, is the complexity $O(n^3)$? Does it go up as $O(n^x)$? Is the non-asymptotic complexity still divided by 2 for orders of 3 or more? Would the numerator be $(n * (n-1) * (n-2))$? How would that be expressed generally for orders of $x$ (would it look like $(n * (n - 1) * ... * (n - (x - 1) ))$?)?
