Is it O(n) or O(1) (by saving the length in a private variable during string allocation to the object)?
if it is O(n), does it mean that the complexity of following code is O(n^2)?
for(int i=0; i<s.length()-1;i++){ //some code here! } 
- 1FYI java is open source, you can check what it does yourself ;)RamonBoza– RamonBoza2013-11-28 11:01:01 +00:00Commented Nov 28, 2013 at 11:01
- 4@RamonBoza Actually OpenJDK is open source. Java is a specification and has no intrinsic source code.Marko Topolnik– Marko Topolnik2013-11-28 11:18:13 +00:00Commented Nov 28, 2013 at 11:18
Add a comment |
4 Answers
It is O(1) as the length is already known to String instance.
From JDK 1.6 it is visible.
public int length() { return count; } Update
It is important to understand why they can cache the value of count and keep using same value for count. The reason lies in a great decision they took when designing String, its Immutability.
Comments
In Java any String is backed up by an final array. So it is simple to just return the array length. So it is O(1) complexity. And if you think in your code
for(int i=0; i<s.length()-1;i++){ //some code here! } s.length() is called for every iteration then you are not right. Modern compiler optimizes this type of call and changes s.length() to constant number(i.e the length of the String instance).
answered Nov 28, 2013 at 11:04
Anirban Nag 'tintinmj'
5,8086 gold badges44 silver badges67 bronze badges
Comments
String internally maintains an array of characters and length of the array is a property of array object hence O(1) as its simple reading of property.
2 Comments
Aniket Thakur
What do you mean by array object?
Santosh
I have mentioned
array of characters! And an array in java is an object.The complexity is O(1) Since String class have the length as a field. It's not O(n^2).
