Big O Search Algorithms in JavaScript
on
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.
| Test | Ops/sec |
|---|---|
| Find first colour test | 102675741 |
| 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.
| Test | Ops/sec |
|---|---|
| Find colour by colour name | 53659755 |
| 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!
| Test | Ops/sec |
|---|---|
| Find colour by colour name | 8081984 |
| 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.
| Test | Ops/sec |
|---|---|
| Find number index by number - FindItem | 26349 |
| Find number index by number - Binary Search | 844153 |
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:
| Test | Ops/sec |
|---|---|
| Find colour by colour name | 51804043 |
| Find colour by colour name - Binary Search | 7902378 |
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);
});
| Test | Ops/sec |
|---|---|
| Find numbers - linear | 6045812 |
| Find numbers - Binary Search | 6116343 |
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.
