This week's book giveaway is in the Clojure forum.
We're giving away four copies of Clojure in Action and have Amit Rathore and Francis Avila on-line!
See this thread for details.
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

O(n) of string.length()

 
Jacob Sonia
Ranch Hand
Posts: 179
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
what is the time complexity of string.length() function. Please explain the reason as well.
 
David O'Meara
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This sounds like homework. Have you checked the source code for that method?
 
David O'Meara
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you can't find it, see here:
http://www.docjar.com/html/api/java/lang/String.java.html
 
Ulrika Tingle
Ranch Hand
Posts: 92
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 13459
Android Eclipse IDE Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic