# Optimizing computational algorithms

Karol Dowbecki · May 29, 2021

When optimizing an algorithm it’s often good to pause, take a step back, and think about the problem domain before jumping straight to coding. Today I have seen following question asked on Stack Overflow:

I have a program that has two nested for loops and takes $$O(n^2)$$ time. I want to know if there is such way to decrease the time of execution for it. Example:

long b = 10000;
long counter = 0;
for (int k = 0; k < b; k++) {
for (int a = k; a < b; a++) {
counter += k;
}
}


At first glance we immediately notice that in the above code variable k is added repeatedly. Perhaps we could remember the counter variable value from the previous loop iteration? Perhaps we could create another variable… Here we should pause and take a step back.

The above code can be represented as a mathematical equation, let’s write it down:

$counter = \sum\limits_{k = 0}^{b-1} \sum\limits_{a = k}^{b-1} k$

The inner sum is $$k$$ added from $$k$$ to $$b-1$$ (inclusive) times. In total $$k$$ is going to be added $$b - 1 - k + 1 = b - k$$ times here. Knowing this we can expand the inner sum:

$\sum\limits_{k = 0}^{b-1} \sum\limits_{a = k}^{b-1} k = \sum\limits_{k = 0}^{b-1} [k(b-k)] = \sum\limits_{k = 0}^{b-1} (kb-k^2) = \sum\limits_{k = 0}^{b-1} kb - \sum\limits_{k = 0}^{b-1} k^2 = b \sum\limits_{k = 0}^{b-1} k - \sum\limits_{k = 0}^{b-1} k^2$

We have converted a sum of sums into two separate sums. In the process removed $$a$$ making it simpler. To solve the two sums we can use known summation formulas, often attributed to Gauss:

$\sum\limits_{a = 1}^{n} a = \frac{n (n+1)}{2} \newline \sum\limits_{a = 1}^{n} a^2 = \frac{n (n+1) (2n+1)}{6}$

If we apply these summation formulas to our equation:

$b \sum\limits_{k = 0}^{b-1} k - \sum\limits_{k = 0}^{b-1} k^2 = b \frac{(b-1) (b-1+1)}{2} - \frac{(b-1) (b-1+1) [2(b-1) + 1]}{6} = \newline = b \frac{(b-1) b}{2} - \frac{(b-1) b (2b-1)}{6} = \frac{b^3- b^2}{2} - \frac{(b^2-b) (2b-1)}{6} = \newline = \frac{b^3- b^2}{2} - \frac{2b^3 - b^2 - 2b^2 + b}{6} = \frac{3b^3 - 3b^2}{6} - \frac{2b^3 - 3b^2 + b}{6} = \newline = \frac{3b^3 - 3b^2 - 2b^3 + 3b^2 - b}{6} = \frac{b^3 - b}{6}$

We have significantly simplified the original nested sum equation into just:

$counter = \frac{b^3 - b}{6}$

which can be implemented as a one-liner:

long counter = (b * b * b - b) / 6;


If you are not believing that the new formula works you can try the code yourself:

public static void main(String[] args) {
for (long b = 0; b <= 10000; b++) {
long counter = original(b);
long fastCounter = fast(b);
System.out.printf("%d\t%d\t%d%n", b, counter, fastCounter);
if (counter != fastCounter) {
System.out.println("Failed");
return;
}
}
System.out.println("Worked");
}

private static long original(long b) {
long counter = 0;
for (int k = 0; k < b; k++) {
for (int a = k; a < b; a++) {
counter += k;
}
}
return counter;
}

private static long fast(long b) {
return (b * b * b - b) / 6;
}


You will observe:

9995	166416789980	166416789980
9996	166466744990	166466744990
9997	166516709996	166516709996
9998	166566684999	166566684999
9999	166616670000	166616670000
10000	166666665000	166666665000
Worked


This new fast algorithm has a runtime complexity of just $$O(1)$$ and great performance with just 4 arithmetic operations. We can always strive to improve this new approach, taking care of edge cases like integer overflow. However, this might already be the optimal solution.