BUT..

When you need to create something special which is requires a lot of functionality, performance and complexity then you need to know about big o notation.

O stands for operation

Here is the chart of operations size

Now let’s see examples of complexity below 👇

Constant runtime O(1)

const dataObject = {
 key: "value",
 name: "John",
 lastName: "Smith"
};

// We always getting current item with one operation
dataObject["key"];

This means that no matter what data object changes or becomes larger, our operation will remain the same.

Another example of O(1) with array

const dataArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

// Here we always getting current index
dataArray[4]; // 5

Logarithmic time complexity O(log N)

function binarySearch(arr, val) {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);

    if (arr[mid] === val) {
      return mid;
    }

    if (val < arr[mid]) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }

    console.log(start, end);
    console.log('Operations count');
  }
  return -1;
}

const data = Array.from(Array(4_000).keys());
console.log(binarySearch(data, 498));

For the logarithmic runtime, we have a good example of binary search, which essentially splits a sorted array into two, then checks whether our search number is equal to more or less than the number found, and repeats this until we get the exact one. In this example, we sorted the index array from 0 to 3999 and got the exact index after 11 operations.

Linear time complexity O(N)

const data = Array.from(Array(100).keys());

data.forEach((index) => {
  if (index === 50) { // but 50 can be any number this is just for example
    // do something
  } else {
    // do something else
  }
});

Here we have an index array of size 100, so the execution time should always be equal to the length of the array (100) no matter what we do.

Log linear time complexity O(N log N)

function merge(left, right) {
  let sortedArr = [] // the sorted items will go here
  while (left.length && right.length) {
    // Insert the smallest item into sortedArr
    if (left[0] < right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }
  // Use spread operators to create a new array, combining the three arrays
  return [...sortedArr, ...left, ...right];
}

function mergeSort(arr) {
  // Base case
  if (arr.length <= 1) {
   return arr;
  }
  const mid = Math.floor(arr.length / 2)
  // Recursive calls
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));

  return merge(left, right)
}

console.log(
 mergeSort([12, 34, 11, 1, 54, 25, 67, 45])
);

Let’s look at an example of merge sort, which divides an unsorted array into fragments until only 1 element remains, then compares them and merges them.

Quadratic time complexity O(n²)

function bubbleSort(arr) {
  for ( let i = 0, l = arr.length; i < l; i++ ) {
    for ( let j = 0; j < l; j++ ) {
      const temp = arr[i];

      if (arr[i] < arr[j]) {
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }

  return arr;
}

console.log(
 bubbleSort([12, 34, 11, 1, 54, 25, 67, 45])
);

Let’s imagine that we have an array of numbers and our task is to sort them in ascending order, so one way to do this is to use the bubble sort algorithm. The basic idea is to compare the current number with all the others and swap them if necessary.

Cubic time complexity O(n³)

function CubicFunction(arr) {
  for ( let i = 0, l = arr.length; i < l; i++ ) {
    for ( let j = 0; j < l; j++ ) {
      for ( let m = 0; m < l; m++ ) {
        console.log( `i:${i}, j:${j}, m:${m}` );
      }
    }
  }

  return arr;
}

CubicFunction([12, 34, 11, 1, 54, 25, 67, 45]);

This runtime example is similar to bubble sort with the difference that it has three levels of iteration depth.

Exponential time complexity O(2^n)

const recursiveFibonacci = (n) => {
  if (n < 2) {
    return n;
  }

  const result = recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);

  return result;
};

console.log(`Result: ${recursiveFibonacci(8)}`); // 21

Let’s see the example of fibonacci recursive function, where the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones.

Factorial time complexity O(n!)

function factorial(n){
  
  if (n === 0) {
    return 1;
  }

  return n * factorial(n - 1);
}

console.log( factorial(2) ); // 2 operations
console.log( factorial(3) ); // 6 operations
console.log( factorial(4) ); // 24 operations
console.log( factorial(5) ); // 120 operations

/* Example of factorial 2
12 21

/* Example of factorial 3
132 123
231 213
321 312

/* Example of factorial 4
1234 2431 3412 4123
1243 2413 3421 4132
1423 2341 3214 4213
1432 2314 3241 4231
1342 2143 3142 4321
1324 2134 3124 4312

etc...
*/

This is the worst case scenario of all the previous ones, so what we do here is we simply count all the available scenarios for the current combinations.

Conclusion

Congratulations, you now know all the popular complexity runtimes. I wish you to find interest in what you creating, have fun, and most importantly, enjoy the process! 😊

Codepan link: https://codepen.io/pen?template=LYvNKWK

Today I’ll show you how to create optimized virtual scroll using pure HTML+CSS+JS.

In the modern www (World Wide Web), many problems arise related to DOM optimization, and we will solve one of them here today.

Let’s imagine that we have very large data coming from the server and we need to display it in a scroll <div>.

But we don’t want/need to show all of them cause it can affect on performance.

What to do?

Let’s create index.html file with the following content 👇

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Virtual scroll</title>
    <style>
       * { box-sizing: border-box; margin: 0; padding: 0; }
       body { background-color: #838383; font-family: Helvetica, Arial, sans-serif; }
       .scroll { margin: 0 auto; width: 600px; }
       .scroll__wrapper { background-color: #FFFFFF; border: 2px solid #999999; max-height: 400px; overflow: auto; }
       .scroll__wrapper::-webkit-scrollbar { background-color: #EEEEEE; height: 10px; width: 10px; }
       .scroll__wrapper::-webkit-scrollbar-thumb { background: #000000; border-radius: 8px; }
       .scroll__item-number { color: #FFFFFF; font-size: 40px; height: 60px; line-height: 60px; margin: 20px 0; text-align: center; }
       .scroll__content { border-bottom: 1px solid #999999; margin-bottom: 10px; padding: 10px; }
       .scroll__title { font-size: 16px; margin-bottom: 10px; }
       .scroll__text { font-size: 14px; display: -webkit-box; -webkit-line-clamp: 3; -webkit-box-orient: vertical; overflow: hidden; }
       .scroll__start-padding,
       .scroll__end-padding { background: repeating-linear-gradient(#EEEEEE, #EEEEEE 10px, #FFFFFF 20px, #FFFFFF 25px); }
   </style>
  </head>
  <body>
   <div class="scroll">
     <div class="scroll__item-number">0</div>
     <div class="scroll__wrapper">
       <div class="scroll__start-padding"></div>
       <div class="scroll__list"></div>
       <div class="scroll__end-padding"></div>
     </div>
   </div>
   <script src="script.js"></script>
  </body>
</html>

Let’s not dive into css is just a basic view

Now create script.js file with the following code 👇

const initScroll = () => {

 // Functions
 const generateData = (arraySize) => {

  const data = new Array(arraySize).fill({
   name: "John",
   lastName: "Smith",
   text: "Lorem ipsum dolor, sit amet consectetur adipisicing elit. Adipisci eveniet nam laboriosam, quas assumenda tempora fuga ut dignissimos quia consequuntur magnam sit aliquid ex cum quo similique nemo molestiae fugit aliquam repellendus voluptatibus? Delectus itaque sequi cupiditate laboriosam perspiciatis ab."
  });

  return data;
 }

 const getHtmlContent = ({ name, lastName, text, index }) => {

  const htmlTemplate = (
   `<div class="scroll__content" data-index="${index}">
    <h2 class="scroll__title">${name + " " + lastName + " - " + index}</h2>
    <p class="scroll__text">${text}</p>
   </div>`
  );

  return htmlTemplate;
 };

 const getScrollItemHeight = () => {

  const scrollContent = scroll.querySelector(".scroll__content");

  return scrollContent.offsetHeight + parseInt(getComputedStyle(scrollContent).marginBottom);
 };

 const renderItems = () => {

  let content = "",
   startIndex = start;

  while ( startIndex < end ) {

   content += getHtmlContent({...filledArr[startIndex], index: startIndex});

   startIndex++;

  }

  scroll.querySelector(".scroll__list").innerHTML = content;

 };

 const setPaddings = () => {

  const scrollItemHeight = getScrollItemHeight();

  scrollStartPadding.style.height = (start * scrollItemHeight) + "px";
  scrollEndPadding.style.height = ((scrollItemsCount - end) * scrollItemHeight) + "px";
 };

 const debounce = () => {

  let timer = null;

  return (cb, time = 250) => {
   if (timer !== null) {
    clearTimeout(timer);
   }
   timer = setTimeout(cb, time);
  };
  
 };

 const shouldReRender = () => {
  const startItem = scroll.querySelector(`.scroll__content[data-index="${start}"]`);
  const endItem = scroll.querySelector(`.scroll__content[data-index="${end-1}"]`);

  return !startItem || !endItem;
 };

 const onScrollHandler = (e) => {

  const scrollTop = e.target.scrollTop;
  const getScrolledCurrentIndex = Math.floor(scrollTop / getScrollItemHeight()) || 0;

  // Showing in the browser current item index
  scroll.querySelector(".scroll__item-number").innerHTML = getScrolledCurrentIndex;

  scrollEnd(() => {

   // Update start, end items
   start = getScrolledCurrentIndex;
   end = getScrolledCurrentIndex + limit;
   
   // Decreasing displayed items by average of limit in order to have current item in the middle of renderer items
   start -= rendererItemsAverage;
   end -= rendererItemsAverage;

   // Check not to display unavailable items
   if (start <= 0) {
    start = 0;
    end = limit;
   } else if (end >= scrollItemsCount) {
    start = scrollItemsCount - limit;
    end = scrollItemsCount;
   }

   // Check should re-render
   if (shouldReRender()) {
    reRender();
    e.target.scrollTop = scrollTop;
   }

  });
  
 };

 const reRender = () => {
  renderItems();
  setPaddings();
 };

 // Constants
 const limit = 10;
 const scrollItemsCount = 100_000;
 const filledArr = generateData(scrollItemsCount);
 const scroll = document.querySelector(".scroll");
 const scrollWrapper = scroll.querySelector(".scroll__wrapper");
 const scrollStartPadding = scroll.querySelector(".scroll__start-padding");
 const scrollEndPadding = scroll.querySelector(".scroll__end-padding");
 const rendererItemsAverage = Math.floor(limit / 2);
 const scrollEnd = debounce();

 // Variables
 let start = 0,
     end = limit;

 // Init functional
 reRender();
 scrollWrapper.onscroll = onScrollHandler;

};

// Document ready event
document.addEventListener("DOMContentLoaded", initScroll);

Now refresh your browser.

🎉🎉 Huuurah Congrats you have it.

As we can see we have 100.000 array of objects but showing only limited 10 items.

To change the limit just edit limit constant on your own.

Example 👇

const limit = 15;

Now you will have 15 items per scroll.

Codepan link: https://codepen.io/Karapet-Hakobyan/pen/Rwddbrw

Github link: https://github.com/karo73/virtual-scroll