Java: Loop string length time complexity

Question

I am learning Big O notation and am wondering what the time complexity for this for loop would be.

public int loop(String text) { int result = 0; for (int i = 0; i < text.length(); i++) { result += text.charAt(i); } return result; }

I'm not sure if the time complexity would be O(n) or O(1). I know if the loop was going to n I would assume a time complexity of O(n) but I'm not sure if text.length() would mean the same thing.

Havin Leung · Accepted Answer · 2018-04-04 00:19:59Z

4

Let n be the number of characters in your string. Your loop obviously iterates n times (since text.length() == n), with each iteration doing constant work (addition).

Your loop should be O(n)

EDIT: The other answers are wrong. You are not returning a string, nor appending to a StringBuilder. You are adding the int value of each ASCII character, and returning the total.

edited Apr 4, 2018 at 0:19

answered Apr 4, 2018 at 0:00

Havin Leung

3031 silver badge11 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Thorbjørn Lindeijer Over a year ago

Are you just assuming text.length() is O(1) or is this documented somewhere? The C function strlen is O(n), for example.

Havin Leung Over a year ago

In C, strings are null terminated char arrays. You can have a char array of length 200, but if the first null byte is at index 100 you'll have a length of 100. This means you actually have to loop over the string and count each byte until you hit null. IIRC, in Java strings are immutable and hold exactly N characters in the Object's private member field. Then you can get it in O(1) because getting the size of the array is O(1) (it's kept as metadata), and that corresponds exactly to the string length in Java.

Thorbjørn Lindeijer Over a year ago

Yeah, it's quite a safe assumption, but I was just trying to make sure. The documentation for String.length doesn't say anything about its complexity: docs.oracle.com/javase/8/docs/api/java/lang/… (but I guess it would have, if it was somehow O(n) :-)).

Havin Leung Over a year ago

I usually assume that if it's easy to keep it as metadata, then it's probably O(1). E.g. it'd be silly to recompute a Hashmap or List's size every time you query for it rather than just do O(1) work to keep track of it. If you're writing performance sensitive code then you'll want to revisit that assumption and make sure by digging into the documentation or source code (:

Elliott Frisch · Accepted Answer · 2018-04-04 00:02:56Z

It's O(n). However, a simple change can make it O(1) here. Change the method body to return text;. String is immutable; creating a copy character by character is pointless.

Collectives™ on Stack Overflow

Java: Loop string length time complexity

2 Answers 2

4 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Related