Big O Notation and Time Complexity Part 3

In my previews post we went over some examples of time complexity and today we are going to continue with another example for O(n²) — Quadratic time.

Bubble Sort

We want to sort the elements in an array. We can do this is using bubble sort as follows:

function sort(n) {
for (let outer = 0; outer < n.length; outer++) {
let outerElement = n[outer];
for (let inner = outer + 1; inner < n.length; inner++) {
let innerElement = n[inner];
if(outerElement > innerElement) {
// swap
n[outer] = innerElement;
n[inner] = outerElement;
// update references
outerElement = n[outer];
innerElement = n[inner];
 }
  }
   }
return n;
}
sort([3,6,1,5,4,7,9,8,2,10]) ==> 
the result will be [1,2,3,4,5,6,7,8,9,10]

Remember that for a very big N the time it takes to solve the problem will increase. Now we are going to dive into some challenging examples.

O(n^c) — Polynomial-time.

Polynomial running is represented as O(nc), when c > 1 . Remember the time when in math class the teacher asked you to find X?

Let’s find the solutions for the following multi-variable equation:

3x + 9y + 8z = 79

This program will give you all the solutions that satisfy the equation where x, y, and z < n.

function findXYZ(n) {
  const solutions = [];
 for(let x = 0; x < n; x++) {
 for(let y = 0; y < n; y++) {
 for(let z = 0; z < n; z++) {
 if( 3*x + 9*y + 8*z === 79 ) {
 solutions.push({x, y, z});
   }
 }
}
}
return solutions;
}
console.log(findXYZ(6)) 
==> [ { x: 1, y: 4, z: 5 }, { x: 4, y: 3, z: 5 } ]

This is all for today. I’m still going over some more examples to continue this series.