wood burning stoves 2.0*
The moose likes Java in General and the fly likes O(n) of string.length() Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "O(n) of string.length()" Watch "O(n) of string.length()" New topic
Author

O(n) of string.length()

Jacob Sonia
Ranch Hand

Joined: Jun 28, 2009
Posts: 174
what is the time complexity of string.length() function. Please explain the reason as well.
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

This sounds like homework. Have you checked the source code for that method?
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

If you can't find it, see here:
http://www.docjar.com/html/api/java/lang/String.java.html
Ulrika Tingle
Ranch Hand

Joined: Nov 24, 2009
Posts: 92
Jacob Sonia wrote:what is the time complexity of string.length() function. Please explain the reason as well.


In principle you don't know. Either the String class keeps the string's length in a variable. In that case this variable is just returned by length() and you get constant complexity, that is O(1).

Or the String class has no such internal variable. This would mean length() must scan the string to find out how long it is and that means linear complexity, or O(n).

From what I can see the Sun Java documentation for String doesn't offer any answer as to what's the case. This means that you don't know whether length() of String is O(1) or O(n) really.

Quite chocking isn't it.
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

Ulrika Tingle wrote:From what I can see the Sun Java documentation for String doesn't offer any answer as to what's the case.

Which is a good point. Assuming that there is only a single Java implementation and making decisions based on the undocumented internals of the code would possibly (even probably) lead to problems later down the track.
Unless the Java language Specification dictates any behaviour, nothing is guaranteed. While it is stated that Strings are immutable, and therefore certain internal properties do not change it is reasonable to expect that there could be coding tricks under the covers designed to reduce their impact on the application, but this does not mean they are implemented consistently across all Java implementations.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: O(n) of string.length()
 
Similar Threads
Length of an array and String
String Problem
length Vs length()
Find a pattern in String
Java character input and modification.