Timing Complexity of another string reverse

[Jacob Sonia]

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

    
Scanner in = new Scanner(System.in);
  String a = in.nextLine();
  int len = a.length();
  int lenb = len/2;
  char temp = 0;
  char[] b = a.toCharArray();
  for(int i = 0; i < lenb; i++){
   temp = b[i];
   b[i] = b[len - 1  -  i];
   b[len - 1 - i] = temp;
  }

[Ulrika Tingle]

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]

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]

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:

int len = a.length();   
int lenb = len/2;   
char temp = 0;   
char[] b = new char[len];
for(int i = 0; i < lenb + 1; i++) // the +1 is needed to copy the middle element as well if the length is odd
{   
    b[i] = a.charAt(len - 1 - i);
    b[len - 1 - i] = a.charAt(i);
}  

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.