Why it seems to cost more for a big string to get length? What's the complexity string.length?

Question

According to time complexity or hidden cost of <Array Name>.length in java , it's a O(1) operating for an array to get length in java. As String is an array of char, I think it is the same.

But when I do a simple test:

public static void main(String args[]) {
    String a = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
    for (int i = 0; i < 23; i++){
        long start = System.nanoTime();
        int l = a.length();
        long end = System.nanoTime();
        System.out.println("length: " + l + " cost: " + String.valueOf(end - start));
        a = a + a;
    }
}

And get

length: 100 cost: 395
length: 200 cost: 395
length: 400 cost: 395
length: 800 cost: 394
length: 1600 cost: 395
length: 3200 cost: 394
length: 6400 cost: 395
length: 12800 cost: 394
length: 25600 cost: 394
length: 51200 cost: 395
length: 102400 cost: 789
length: 204800 cost: 789
length: 409600 cost: 1974
length: 819200 cost: 790
length: 1638400 cost: 3158
length: 3276800 cost: 3553
length: 6553600 cost: 4342
length: 13107200 cost: 3552
length: 26214400 cost: 2368
length: 52428800 cost: 6711
length: 104857600 cost: 3158
length: 209715200 cost: 1974

It seems the length operating cost much more when there are more than 400000 characters.

Did I miss or misunderstand something?

https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — Oliver Charlesworth, Jun 05 '17 at 11:46
https://stackoverflow.com/questions/254726/in-java-for-a-string-x-what-is-the-runtime-cost-of-s-length-is-it-o1-or-o — Akshar Patel, Jun 05 '17 at 11:53

score 1 · Accepted Answer · answered Jun 05 '17 at 11:49

1

String.length() is indeed O(1). If you look in the class (available since Java 1.6) it returns a field.

public int length() {
    return value.length;
}

So I would say your benchmark technique must be introducing error.

answered Jun 05 '17 at 11:49

Demogorii

656
5
16

Why it seems to cost more for a big string to get length? What's the complexity string.length?

1 Answers1