SPOILER ALERT. Working solution here. Don’t look in code if you wanna do it on your own.
Using some cool trick for dealing with nested loops. Such hint was kindly given to me in this thread
Wondering maybe I can optimize this code even more? No ideas for now.
function sumSquareDifference(n) {
//assume have case >>> n = 3
//sum of the squares >>> 1^2 + 2^2 + 3^2
//square of the sums >>> 1^2 + 2^2 + 3^2 + 2(1 * 2) + 2 (1 * 3) + 2 * (2 * 3)
//difference is obvious
//need to find sum of products of pair combos of numbers from 1 to n
//then multiply it by 2
let result = 0;
for (let i = 1; i <= n; i++) {
//inner loop optimized >> to avoid duplicates
//>>to avoid squares like (1 * 1)
//to reduce loop steps (bigO better than O(n^2) here)
for (let j = i + 1; j <= n; j++) {
result += i * j;
}
}
return 2 * result;
}
sumSquareDifference(100);
I don’t know that this changes the big O of the algorithm.
There is a direct formula for the sum.
My logic was:
if we have something like
case 1
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; i++) {
console.log(i,j)
}
}
Above will be 3^2 lines in the console, and it’s classic nested loops O(n^2) situation
If we have some stuff like in solution
case 2
for (let i = 0; i < 3; i++) {
for (let j = i; j < 3; i++) {
console.log(i,j)
}
}
there will be 6 lines in the console. Its less complexity or not? Both cases are scalable, if we will increase size of the problem.
It is less iterations, but both iteration counts scale as O(n^2). Big O is all about the biggest term in the number of operations.
Your loops iterate n-1 + n-2 +… + 1 times, which is ~n^2 iterations.
1 Like
My research just led me to something called Efficient Polynomial-Time Nested Loop Fusion
But there is too much math terminology and my English is failing a little when it comes to maths.
When you answered, I was in the middle of some coding experiment, so I coded this:
note: not sure how can I call it? test function/ research function…?
Not sure if it is useful at all tho 
//compare number of iterations
const countNumberOfIterations = (minSize, maxSize, step) => {
//will print comparison for each problem size rom 1 to n
for (let problemSize = minSize; problemSize <= maxSize; problemSize += step) {
let countClassic = 0;
let countJequalI = 0;
for (let i = 0; i < problemSize; i++) {
for (let j = 0; j < problemSize; j++) {
countClassic++;
}
}
for (let i = 0; i < problemSize; i++) {
for (let j = i; j < problemSize; j++) {
countJequalI++;
}
}
console.log('For the problemsize ' ,problemSize);
console.log('Classic loops do ', countClassic, ' iterations.')
console.log('J equal I situation gives ', countJequalI, ' iterations.');
console.log('Relative complexity(classic to jequali)', countClassic/countJequalI)
console.log('-----------------')
}
}
countNumberOfIterations(10, 100, 10);
/*
For the problemsize 10
Classic loops do 100 iterations.
J equal I situation gives 55 iterations.
Relative complexity(classic to jequali) 1.8181818181818181
-----------------
For the problemsize 20
Classic loops do 400 iterations.
J equal I situation gives 210 iterations.
Relative complexity(classic to jequali) 1.9047619047619047
-----------------
For the problemsize 30
Classic loops do 900 iterations.
J equal I situation gives 465 iterations.
Relative complexity(classic to jequali) 1.935483870967742
-----------------
For the problemsize 40
Classic loops do 1600 iterations.
J equal I situation gives 820 iterations.
Relative complexity(classic to jequali) 1.951219512195122
-----------------
For the problemsize 50
Classic loops do 2500 iterations.
J equal I situation gives 1275 iterations.
Relative complexity(classic to jequali) 1.9607843137254901
-----------------
For the problemsize 60
Classic loops do 3600 iterations.
J equal I situation gives 1830 iterations.
Relative complexity(classic to jequali) 1.9672131147540983
-----------------
For the problemsize 70
Classic loops do 4900 iterations.
J equal I situation gives 2485 iterations.
Relative complexity(classic to jequali) 1.971830985915493
-----------------
For the problemsize 80
Classic loops do 6400 iterations.
J equal I situation gives 3240 iterations.
Relative complexity(classic to jequali) 1.9753086419753085
-----------------
For the problemsize 90
Classic loops do 8100 iterations.
J equal I situation gives 4095 iterations.
Relative complexity(classic to jequali) 1.978021978021978
-----------------
For the problemsize 100
Classic loops do 10000 iterations.
J equal I situation gives 5050 iterations.
Relative complexity(classic to jequali) 1.9801980198019802
-----------------
*/
So there is just some simple formula for that somewhere? And inside function will be one line of code basically?
I’ve heard that some euler problems can be solved with pencil/paper tools.
EDIT. I guess I found that on fCC page with solution.
By the way, on the page with solution to this problem some strange stuff is going on.
In explanation of the problem there are blank lines where formulas should be.
Followed up question(to make sure):
O(n^2) and O(n^3) >>> this is one class of complexity? Can I say that it’s all one class of complexity, which is O(n^c)?
And different class of complexity would be, for example O(c^n)?
Yeah, there exists a formula.
O(n^2) and O(n^3) are different complexity classes.