Evaluating two functions according to their performance

Question

 //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?

Answer 1

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.

• Mustafa Guner: Very clean and informative answer. I appreciate that!