As the title shows, I'm confused with the time complexity of String.substr() method, My guess is it's constant instead of linear, but I can't find the detail explanation by googling. Anybody help?
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.
formerly known as M
Mark
formerly known as M
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 beO(n)in the absence of optimizations. (Notenis 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), wheremis 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)andO(n+m). I'd guessO(m)is most likely.