Time complexity of Java's substring()

70

12

What is the time complexity of the String#substring() method in Java?

TimeToCodeTheRoad

Posted 2011-01-13T11:57:54.517

Reputation: 2 684

@i think since it is a library function that is used quite often, sun must have optimised for it :). so O(1) – TimeToCodeTheRoad – 2011-01-13T12:05:38.510

Answers

102

New answer

As of update 6 within Java 7's lifetime, the behaviour of substring changed to create a copy - so every String refers to a char[] which is not shared with any other object, as far as I'm aware. So at that point, substring() became an O(n) operation where n is the numbers in the substring.

Old answer: pre-Java 7

Undocumented - but in practice O(1) if you assume no garbage collection is required, etc.

It simply builds a new String object referring to the same underlying char[] but with different offset and count values. So the cost is the time taken to perform validation and construct a single new (reasonably small) object. That's O(1) as far as it's sensible to talk about the complexity of operations which can vary in time based on garbage collection, CPU caches etc. In particular, it doesn't directly depend on the length of the original string or the substring.

Jon Skeet

Posted 2011-01-13T11:57:54.517

Reputation: 1 070 456

8No, something like this should be documented. A developer should be aware, just in case he plans to take a small substring of a large string, expecting the larger string to be garbage collected like it would be in .NET. – Qwertie – 2012-06-22T21:10:00.777

The original question is super-old, but please notice that this answer does NOT apply anymore. Check Chi answer or the source of the function. @JonSkeet maybe edit the answer – LyK – 2014-03-19T19:33:42.330

1@LyK: Done, thanks. – Jon Skeet – 2014-03-20T07:04:31.613

11+1 for "undocumented", which is an unfortunate weakness of the API. – Raedwald – 2011-01-13T12:43:18.687

9It's not weakness. If behavior is documented, and implementation details are not, it allows faster implementations in the future. In general, Java often defines behavior and lets implementations decide what's best way. In other words - you should not care, after all, it's Java ;-) – peenut – 2011-01-13T15:37:01.927

It's worth noting that although performance is worse, this change was made to address a gc leak

– Krease – 2015-10-01T23:59:25.877

Is it linear in the number of characters of the original string or in the number of copied characters? – Ivaylo Toskov – 2016-02-13T18:17:27.323

1@IvayloToskov: The number of copied characters. – Jon Skeet – 2016-02-14T09:12:50.600

We should update this answer to be more exact - it is confusing because usually when we say O(n) for a string, it refers to the number of chars in the string, whereas this is O(m) where m is length of the substring. Thus, if we have stringNChars.substring(a,a+m) (where m is length) then it is O(m), not O(n). – user151975 – 2017-07-26T21:37:05.320

1@user151975: Sure, updated. – Jon Skeet – 2017-07-27T06:53:13.323

2Good point peenut, even if I hardly believe they will ever manage to make this one faster than O(1). – abahgat – 2011-08-12T16:04:20.207

28

It was O(1) in older versions of Java - as Jon stated, it just created a new String with the same underlying char[], and a different offset and length.

However, this has actually changed started with Java 7 update 6.

The char[] sharing was eliminated, and the offset and length fields were removed. substring() now just copies all the characters into a new String.

Ergo, substring is O(n) in Java 7 update 6

Chi

Posted 2011-01-13T11:57:54.517

Reputation: 17 882

1+1 This is indeed the case in recent Sun Java and OpenJDK versions. GNU Classpath (and others, I assume) are still using the old paradigm. Unfortunately there seems to be a bit of intellectual inertia w.r.t. this. I still see posts in 2013 recommending various approaches based on the assumption that substrings use a shared char[]... – thkala – 2013-02-04T18:40:09.833

6So new version no longer have O(1) complexity. Curious to know is there any alternative way to implement substring in O(1)? String.substring is an extremely useful method. – Yitong Zhou – 2013-06-05T00:39:51.553

5

It's now linear complexity. This is after fixing a memory leak issue for substring.

So from Java 1.7.0_06 remember that String.substring now has a linear complexity instead of a constant one.

friends.pallav

Posted 2011-01-13T11:57:54.517

Reputation: 51

So it is worse now (for long strings)? – Peter Mortensen – 2018-02-08T20:19:03.290

@PeterMortensen yes. – Ido Kessler – 2018-04-28T08:04:48.657

2

O(1) because no copying of the original string is done, it just creates a new wrapper object with different offset information.

rodion

Posted 2011-01-13T11:57:54.517

Reputation: 11 909

1

Judge for yourself from following, but Java's performance drawbacks lie somewhere else, not here in substring of a string. Code:

public static void main(String[] args) throws IOException {

        String longStr = "asjf97zcv.1jm2497z20`1829182oqiwure92874nvcxz,nvz.,xo" + 
                "aihf[oiefjkas';./.,z][p\\°°°°°°°°?!(*#&(@*&#!)^(*&(*&)(*&" +
                "fasdznmcxzvvcxz,vc,mvczvcz,mvcz,mcvcxvc,mvcxcvcxvcxvcxvcx";
        int[] indices = new int[32 * 1024];
        int[] lengths = new int[indices.length];
        Random r = new Random();
        final int minLength = 6;
        for (int i = 0; i < indices.length; ++i)
        {
            indices[i] = r.nextInt(longStr.length() - minLength);
            lengths[i] = minLength + r.nextInt(longStr.length() - indices[i] - minLength);
        }

        long start = System.nanoTime();

        int avoidOptimization = 0;
        for (int i = 0; i < indices.length; ++i)
            //avoidOptimization += lengths[i]; //tested - this was cheap
            avoidOptimization += longStr.substring(indices[i],
                    indices[i] + lengths[i]).length();

        long end = System.nanoTime();
        System.out.println("substring " + indices.length + " times");
        System.out.println("Sum of lengths of splits = " + avoidOptimization);
        System.out.println("Elapsed " + (end - start) / 1.0e6 + " ms");
    }

Output:

substring 32768 times
Sum of lengths of splits = 1494414
Elapsed 2.446679 ms

If it is O(1) or not, depends. If you just reference same String in memory, then imagine very long String, you make substring and stop referencing long one. Wouldn't be nice to release memory for long one?

peenut

Posted 2011-01-13T11:57:54.517

Reputation: 2 322