I think it depends on two things:

• Can indexing be done in constant time? (O(1)).

  This seems that'd be obvious, but if strings are stored as flexible-width like utf8, you can index bytes in constant time, but not characters. They'd be O(n) in the absence of optimizations. (Note n is the length of the original string).

  I'm not sure what Javascript uses or whether it's implementation dependent.

• Is a copy made, or does Javascript return a 'slice' that just refers to the existing string?

  If a copy is made, then is takes O(m), where m is the length of the copy.

  Strings in Java are immutable, so it'd be possible to return a view/slice instead of copying. That would be an O(1) operation. But I don't know if it does that or if it's implementation dependent.

So somewhere between O(1) and O(n+m). I'd guess O(m) is most likely.

Thank you. So for the following code, which is used to get all the sub string with length k from a string:

function fun1(str, k) {
  let rtn = [];
  for (let i = 0; i < str.length - k + 1; i++) {
    let current = str.substr(i, k);
    rtn.push(current)
  }
  return rtn;
}

the time complexity is O(n*k), which is approximated to O(n), right? I guess so. Thank you.

hashnode.com/post/can-anyone-give-me-a-comprehens… check the explanation of Todd.

And after that think about what substr needs to do. if a string is an array of characters and you can access every position but you have to select a range

so if k is the length of the range and n is the length of the string it would be O(k). The big O notation is a lot about perspective.