2

What is time complexity of javascript's substring method?

I think implementation of this method may be same as Java but for Java now substring has O(N) complexity from Java7 onwards and O(1) for pre-Java7.

Aman Gupta
  • 3,627
  • 4
  • 40
  • 64
  • have you done any effort to find it? – Sagar V Apr 05 '17 at 06:16
  • I doubt substring can have O(1) complexity considering strings can vastly vary in length. I'm imagining O(n) at best, but I don't know f about Java – Mulan Apr 05 '17 at 06:16
  • In my understanding it should be `O(N)` as string internally is an array of characters – Rajesh Apr 05 '17 at 06:17
  • _"I think implementation of this method may be same as Java"_ -> [What's the difference between JavaScript and Java?](http://stackoverflow.com/questions/245062/whats-the-difference-between-javascript-and-java) – Andreas Apr 05 '17 at 06:17
  • 1
    I imagine if would be O(n). Interestingly you can do your own analysis of the algorithms time complexity by feeding in your own strings – Barney Chambers Apr 05 '17 at 06:18
  • 1
    @SagarV This question does not seems to be asked on stackoverflow before and hence qualifies to be asked here. And believe me I did my research before asking the simple question. If for you research means looking into source code and writing code to find complexity then no. – Aman Gupta Apr 05 '17 at 06:21
  • @naomik The best substring algorithm is actually O(n/m) where m is the length of the substring (needle). Google Boyer-Moore algorithm. – slebetman Apr 05 '17 at 06:28
  • @slebetman Are you confusing string search with substring? – Bergi Apr 05 '17 at 07:03
  • @Bergi Ah yes. Sorry. In which case best case substring should be O(1). Why should it be anything else unless you implement strings as linked lists (or ropes) – slebetman Apr 05 '17 at 07:10
  • @slebetman yes, exactly that: not all strings are necessarily represented as contiguous slices of memory, e.g. the results of concatenations. Also, keeping only references around is a horror for garbage collection. – Bergi Apr 05 '17 at 07:24
  • Looks like it is O(n) because a new memory is allocated for each substring operation. – Aman Gupta Apr 05 '17 at 09:41

0 Answers0