Trade-Offs Between Time and Space
In Chapter 4, Speeding Up Your Code with Big O, we wrote a JavaScript function that checked whether an array contained any duplicate values. Our first version looked like this:
| function hasDuplicateValue(array) { |
| for(var i = 0; i < array.length; i++) { |
| for(var j = 0; j < array.length; j++) { |
| if(i !== j && array[i] == array[j]) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
It uses nested for loops, and we pointed out that it has a time complexity of O(N2).
We then created a more efficient version, which looked like this:
| function hasDuplicateValue(array) { |
| var existingNumbers = []; |
| for(var i = 0; i < array.length; i++) { |
| if(existingNumbers[array[i]] === undefined ... |
Get A Common-Sense Guide to Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.