Data structure and Algorithm: Big O

Problem-solving is a critical aspect of our journey as developers, and one of the best ways by which we can give ourselves a big boost when it comes to problem-solving is by learning Data Structures and Algorithms.

What is Data Structure?

A data structure is simply a programmatic means of storing data so it can be used efficiently.

What is an Algorithm?

An algorithm is a step-by-step procedure followed in totality to achieve the desired goal. Algorithms are independent of programming languages, they can be written for any language.

BIG O

There are two main characteristics that can be given to codes before they can be classified as good codes. These characteristics are:

1. Readability.
2. Scalability.

BIG O Asymptotic Analysis helps us determine the scalability of our codes. When it comes to Big O, we can ask ourselves certain questions like:

1. How long does it take to run a problem or a task ?. This can be considered as the ( Time Complexity) of a problem.
2. What is the amount of memory being consumed when a problem is run? This is considered as the (Space Complexity) of a problem.

There are key notations to put in place when considering Big O:

Big O chart from Big O cheatsheet

1. O(1) — Constant Time:

This has the least complexity when it comes to time and space, this means your code takes up less memory space and is executed in the shortest time possible. An example can be:

 function LogElement(array) {   
      console.log(array[0]);
}

The above javascript function can be considered as an O(1) because it always prints the element of index 0 whenever it runs, which makes it execute in the shortest time possible.

2. O(n) — Linear Time:

The linear time can be described as an increase in operations as the elements increase. Linear time is the second most effective Big O notation when it comes to time and space complexity. An example would be:

function LoopThroughBoxesArrayAndFindBlue(boxes) {
   for (var i = 0; i < boxes.length; i++) {
      if(boxes[i] === 'Blue') {
         console.log("Found Blue")
      }
   }
}

The above can be considered as O(n) because this loop runs n times and we can’t determine the number of times the loop would run before we find “BLUE”.

3. O(n²) — Quadratic:

This can occur when we have nested loops. When we encounter such cases, we have to think of effective ways to turn our solution into O(n). Solutions with O(n²) during a whiteboard interview can be considered as our first and least effective solution to a problem.

function printPairs(boxes) {
  
  for (var i = 0; i < boxes.length; i++){
    for (var j = 0; j < boxes.length; j++){
      console.log (boxes[i] , boxes[j])
    }
  }
}
const x = [1,2,3,4,5]
printPairs(x)

One cheat of Big O is to always know that a loop is always regarded as O(n), having a nested loop becomes O(n * n) which becomes O(n²).

Other Big O notations are:
1. O(n³) — Cubic
2. O(log n) — Logarithmic
3. O(n!) — Factorial Time (This is also known as the OH NO. haha)

RULES OF BIG O

1. Worst Case — we have to always consider and talk about the worse possible time required for program execution whenever we encounter a problem, then we can think further on how to optimize the solution into the best execution time possible.

2. Remove Constants — we find ways to eliminate all constants when finding the Big O of a function and reduce the Big O notation into an O(n).
In a case where we arrive at O(1 + n + 100 ), we can say n has a larger value because n can be any value, when this occurs, we drop the constants and have O(n).

3. Different Terms For Inputs — Most people tend to fail at interviews when asked the Big O of different terms, in such cases, we need to pay attention to input terms…The sample code below explains this

function LoopThroughArray(boxes) {
  boxes.forEach(boxes1 => {
    console.log(boxes1)
  })
  boxes.forEach(boxes1 => {
    console.log(boxes1)
  })
}

The Big O of the above function would be O(n + n) which is O(2n) which then becomes O(n) when we drop the constants. Now when we look at Different Terms.

function LoopThroughArray(box, boxes) {
  box.forEach(boxes1 => {
    console.log(boxes1)
  })
  boxes.forEach(boxes1 => {
    console.log(boxes1)
  })
}

Pay attention to the naming. Most people refer to this as O(n) which is quite wrong, the Big O of such a case becomes O(a + b) because the size of each input can differ, boxes can have a size of 100 and boxes can have a size of 1000. Because we have two for loops does not mean they loop over the same items.

4. Drop Non-Dominant Terms — When it comes to Big O, we tend to drop the least dominant term. For example, we arrive at a Big O notation O(x² +3x + 100 + x/2) in this case x² is more dominant than the 3x, 100, and x/2 because when it comes to Big O we look at scalability.

For more information about Big O check this article and this great course.

Hope you had a great time learning!!!

Feel free to follow me for more…