• Post Reply Bookmark Topic Watch Topic
  • New Topic

Timing Complexity of another string reverse  RSS feed

 
Jacob Sonia
Ranch Hand
Posts: 183
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all,

First of all i am not trying to do any homework...i am trying to learn programming...and trying to know exactly how can i calculate the o(n) of my programs and understand which code is more optimized. Here;s another code of the same string reversal and i want to know exactly how are you going to calculate the complexity and understand if this code is optimal. Also please help me with a good code of string reversal which is more optimized in terms of performance or tell me what i am doing is good. Thanks to all for your support

 
Ulrika Tingle
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jacob Sonia wrote:please help me with a good code of string reversal


It's so simple.

You just swap elements down to the middle.

It's an n/2 operation.
 
Jacob Sonia
Ranch Hand
Posts: 183
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But, what about the complexity of str.length() and str.toCharArray(). Just wanted to confirm that when determining the complexity of a problem, don't we check all these conditions which lead to the increase in complexity
 
Rob Spoor
Sheriff
Posts: 21133
87
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
String.length() usually is instant, O(1), but as said in your other thread that does not need to be the case. toCharArray is O(n) though, as specified in the Javadoc:
Returns:
a newly allocated character array whose length is the length of this string and whose contents are initialized to contain the character sequence represented by this string.
That array must be filled, and that is an "n" operation.

If you need a char[] then you can make it an n/2 operation again by creating a new array yourself and using charAt:
Of course, if you then use that char[] to create a String that's an "n" operation again so all your performance gains have been voided.

Please note that an "n/2" operation is still O(n); if n duplicates, so does n/2.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!