programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Timing Complexity of another string reverse

Jacob Sonia
Ranch Hand
Posts: 183
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

It's so simple.

You just swap elements down to the middle.

It's an n/2 operation.

Jacob Sonia
Ranch Hand
Posts: 183
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
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.