0

I was trying to make a code working like Array.prototype.indexOf with big O(n).
it is how I calculate Big O of my code. is it right?

n = haystack.length
when it comes to the worst case, which is when the target is located at the end of haystack I guess.

1st time running O(n) => because there is one for loop,
2nd time running O(n-1) => recursively invoke function
3rd time running O(n-2)
...
k-th time running O(n-k)

when it sum all together
O(n) + O(n-1) + O(n-2) + .... + O(n-k); = 2n^2 - 3/2nk ==> O(n^2);

am I right? if Im not, then please let me know how to calculate time complexity of my code.
thanks and stay safe

var strStr = function(haystack, needle) {
  let result;
  let isFirst = false;
  
  return (function recursiveStrStr (haystack, needle) {
      if (!needle) return result = 0;
      if (!haystack) return result = -1;

      let j = 0;
      for (let i = 0; i < haystack.length; i++) {
        if (haystack[i] === needle[j]) {
          if (!isFirst) {
            result = i;
            isFirst = true;
          }
       
          needle = needle.slice(j + 1);
          haystack = haystack.slice(i + 1);
          return (!needle) ? result : recursiveStrStr(haystack, needle);
          
          }
      }
      return -1;

  })(haystack, needle);
}
Han
  • 1
  • strStr("cbca", "ca") returns 0, was that supposed to happen? –  Sep 08 '20 at 16:47
  • that wasn't supposed to happen to solve the problem. but I couldn't calc its time complexity with cases it works properly, so I wanna ask~ thnks – Han Sep 09 '20 at 19:21
  • Correctness plays a part. It's harder to analyze code that's confused about what it's doing. –  Sep 09 '20 at 21:34
  • slice is O(N) - [source](https://stackoverflow.com/questions/22614237/javascript-runtime-complexity-of-array-functions), the code will for certain input slice its way through the haystack one by one, which gets you O(N^2). If you replaced the slice with a constant-time operation, I believe you could have O(N). –  Sep 09 '20 at 21:42

0 Answers0