0
\$\begingroup\$

        //Function-A
        function duplicatesNumber(text) {
            var counts = {};
            let textLowered = text.toLowerCase();
            textLowered.split("").forEach(function (x) {
                counts[x] = (counts[x] || 0) + 1;
            });
            return Object.entries(counts).filter(arr => arr[1] > 1).length
        }

        //Function-B
        function duplicateCount(text) {
            return text.toLowerCase().split('').filter(function (val, i, arr) {
                return arr.indexOf(val) !== i && arr.lastIndexOf(val) === i;
            }).length;
        }
       
       //Function-B
         let start = performance.now();
        console.log(duplicateCount("aaBBcDDcefgheeaas"))
        let end = performance.now();
        console.log("Function-B: "+ (end-start));
     
         
        
         //Function-A
         let start1 = performance.now();
        console.log(duplicatesNumber("aaBBcDDcefgheeaas"))
        let end1 = performance.now();
        console.log("Function-A: "+ (end1-start1))
         

  • I have two functions they both do the same thing. Return the number of duplicates.
  • My question is about their performances. I have just started to learn data structures and algorithms in javascript. I covered Big O'Notation. But I didn't get it correctly I guess.
  • Since Function-A has for each method which means it is O(n) clearly. Isn't that mean Function-A should be slower than the second one? How can be Function-A is faster than Function-B?
\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

Time Complexity

  • Function A cost \$\mathcal{O}\left(n\right)\$
    • toLowerCase, split cost \$\mathcal{O}\left(n\right)\$
    • forEach cost \$\mathcal{O}\left(n\right)\$
    • Object.entries, filter cost \$\mathcal{O}\left(n\right)\$
      • counts[x] read / write may cost \$\mathcal{O}\left(1\right)\$ on average
  • Function B cost cost \$\mathcal{O}\left(n^2\right)\$
    • toLowerCase, split still cost \$\mathcal{O}\left(n\right)\$
    • filter cost \$\mathcal{O}\left(n^2\right)\$
      • indexOf, lastIndexOf cost \$\mathcal{O}\left(n\right)\$
      • filter repeat above operation \$\mathcal{O}\left(n\right)\$ times, thus \$\mathcal{O}\left(n\cdot n\right)\$

Time consume most occurred in loops. Not only forEach, fliter, but also toLowerCase, split, indexOf are loops. You didn't count the performance of nested loops correctly.

Also, notice that big-O notation is targeted to describe how fast the time consume increase when size of input increase. It not necessarily means an algorithm with better big-O notation will always be faster.

Implementation

  • Do not use str.split(''), use [...str] if you can. The split one won't handle some unicode points correctly. For example, [...'𰻝𰻝面'].length is 3 but '𰻝𰻝面'.split('').length is 5.
  • Use Map if you can (no need to support old browsers). Object is not an ideal way to use as a dictionary. Only if you want to keep ES5 support, you may use Object.create(null) instead.
  • You may count how many entries has at least count 2 during iteration by tracking if count[x] == 2 after increase. So there is no need to iterate Object.entries later.
\$\endgroup\$
1
  • \$\begingroup\$ Very clean and informative answer. I appreciate that! \$\endgroup\$ Commented Feb 7, 2021 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.