Bradley Braithwaite
1 import {
2 Learning,
3 JavaScript,
4 AngularJS
5 } from 'bradoncode.com'
6 |

Big O Search Algorithms in JavaScript

on
on javascript, algorithms, binary search

This post provides code examples of some basic algorithms using JavaScript. I'm going to assume some familiarity with JavaScript. I chose JavaScript deliberately so that the sample code can be taken and run in any browser.

For each of the code examples I'm using JSLitmus to provide benchmarks. I will benchmark each method three times with a small, medium and large input. JSLitmus has a useful graph feature that will offer a visual indication of the performance characteristics of each algorithm. It reports how many operations per second are possible under repetitive execution.

It's important to note this is not about benchmarking the algorithms rather I'm using the benchmarks to give a visual indication of the growth characteristics.

To make the examples more succinct they will all make use of the following three arrays.

// Set up a simple array of colours
var colours = new Array ("Black", "Blue", "Brown", "Green", "Pink", "Red", "White", "Yellow");

// Set up numbers from 1 to 2500
var numbersHalf = new Array();
 
for (var i = 1; i < 2500; i++) {
  numbersHalf.push(i);
};

// Set up numbers from 1 to 5000
var numbersFull = new Array();
 
for (var i = 1; i < 5000; i++) {
  numbersFull.push(i);
};

The array colours is the small array, numbersHalf contains 2500 items and numbersFull has 5000 items.

Please refer back the previous blog post to refamiliarise yourself with the concepts.

Constant Complexity

This is expressed as: O(1)

Regardless of the complexity (number of items) the result is constant. The below code will simply take the first item from the array and return it.

// Find the first item
function FindFirstItem(items) {
     return items[0];
}

JSLitmus.test('Find first colour test', function() {
     FindFirstItem(colours);
});
 
JSLitmus.test('Find first number test (2500 items)', function() {
     FindFirstItem(numbersHalf);
});
 
JSLitmus.test('Find first number test (5000 items)', function() {
     FindFirstItem(numbersFull);
});

The table below shows the number of operations per second. As we can see the results are about the same regardless of the number of inputs. The result is constant.

TestOps/sec
Find first colour test102675741
Find first number test (2500 items)99864381
Find first number test (5000 items)99273467


Linear Complexity

This is expressed as: O(n)

With linear complexity the growth rate of the function is directly linked to the number of items. In the code example that follows we are going to iterate over all of the items and match on the last item in the array. Note that when measuring growth we consider the upper bound or worse case scenario, which is why we are looking for the last item in the array in the benchmarks.

function FindItem(items, match) {
     for (var i=0; i < items.length; i++) {
          if (items[i] == match) {
               return true;
          }
     }
     return false;
}

JSLitmus.test('Find colour by colour name', function() {
     FindItem(colours, "Yellow");
});

JSLitmus.test('Find number index by number (2500 items)', function() {
     FindItem(numbersHalf, 2500);
});
 
JSLitmus.test('Find number index by number (5000 items)', function() {
     FindItem(numbersFull, 5000);
});

The below graph clearly shows that more executions per second are possible using the array of colours being that it's much smaller, but it's not terribly useful in comparing the array of 2500 and 5000 items since the results in the graph are relative. From the table data however you can see the comparison.

TestOps/sec
Find colour by colour name53659755
Find number index by number (2500 items)54566
Find number index by number (5000 items)27168
 

Below is the graph of the 2500 vs. 5000 items from the FindItem method. This clearly illustrates the growth rate for twice as many items and that 5000 items is two times slower than 2500.

Logarithmic Complexity

This is expressed as: O(log n)

The following code is just like finding a name in a phone book. Imagine that you are looking for a name in a phone book and you open the book exactly in the middle. If the name you are looking for is not on that page, you move down or up the phone book based on the alphabet and you would find the middle of that section, look for the match and repeat continually moving to the middle of the remaining sections until you find the name you are looking for. Is it very important to note that this is of course is only possible because the phone book is ordered by alphabetically, which provides an index.

This concept is known as a binary search. The code below is an implementation of a binary search:

function FindItemBinarySearch(items, match) {
     
      var low = 0,
          high = items.length -1;
           
      while (low <= high) {
          mid = parseInt((low + high) / 2);

           current = items[mid];
         
          if (current > match) {
             high = mid - 1;
           } else if (current < match) {
              low = mid + 1;
            } else {
              return mid;
           }   
      }       
      
      return -1;
    }
 
JSLitmus.test('Find colour by colour name', function() {
     FindItemBinarySearch(colours, "Yellow");
});
 
JSLitmus.test('Find number index by number (2500)', function() {
     FindItemBinarySearch(numbersHalf, 2500);
});
  
JSLitmus.test('Find number index by number (5000)', function() {
     FindItemBinarySearch(numbersFull, 5000);
});

From the result set below we can see that the colours array list is capable of more executions due to the limited size of the array. Interestingly, there is not much of a difference between the operations per second between the 2500 and 5000 array items. You should now see the gain of using this binary search. Twice as many items but roughly the same performance should speak for itself!

TestOps/sec
Find colour by colour name8081984
Find number index by number (2500 items)3261082
Find number index by number (5000 items)3055804
 

To see a more profound difference we are going to pitch the FindItem method (linear complexity) vs. the FindItemBinarySearch method (logarithmic complexity) when finding the last element in the array of 5000 items.

TestOps/sec
Find number index by number - FindItem26349
Find number index by number - Binary Search844153
 

As you can see, the difference in growth is remarkable.

Linear Complexity vs. Logarithmic Complexity

Before we go rushing off and implementing a binary search for any similar logic in the future we must take a few steps back and consider context.

Let's take the find colour method using linear complexity and compare it with the find colour method using the binary search. Based on what we've seen previously we would expect the binary search to be quicker, right?

Here are the results:

TestOps/sec
Find colour by colour name51804043
Find colour by colour name - Binary Search7902378
 

In this case the linear complexity example is more performant. The extra complexity of the binary search on a small array gives us unnecessary overhead. The lesson here is always consider the context!

I created a second set of benchmarks to identify the point where both methods would equal each other. The code below uses an array with 85 items.

// Set up numbers from 1 to 85 
 JSLitmus.test('Find numbers - linear', function() {
  FindItem(numbers, 85);
 });
 
 JSLitmus.test('Find numbers - Binary Search', function() {
  FindItemBinarySearch(numbers, 85);
 });
TestOps/sec
Find numbers - linear6045812
Find numbers - Binary Search6116343
 

This reinforces the point that when chosing an algorithm we must always consider the context.

Conclusion

It should be apparent based on these examples that Big O notation is not a performance test of an algorithm. It has no concept of context and doesn't take all factors into consideration e.g. varying CPU speeds, Memory usage etc. We also demonstrated that the size of your input can deduce your choice of algorithm. What it does give us is an idea of what we can expect especially when dealing with large data sets.

SHARE
Don't miss out on the free technical content:

Subscribe to Updates

CONNECT WITH BRADLEY

Bradley Braithwaite Software Blog Bradley Braithwaite is a software engineer who works for the search engine duckduckgo.com. He is a published author at pluralsight.com. He writes about software development practices, JavaScript, AngularJS and Node.js via his website . Find out more about Brad. Find him via:
You might also like:
mean stack tutorial AngularJS Testing - Unit Testing Tutorials