Big Moose Saloon
 Search | Java FAQ | Recent Topics Register / Login

# Timing Complexity of another string reverse

Jacob Sonia
Ranch Hand

Joined: Jun 28, 2009
Posts: 171
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

Joined: Nov 24, 2009
Posts: 92

It's so simple.

You just swap elements down to the middle.

It's an n/2 operation.
Jacob Sonia
Ranch Hand

Joined: Jun 28, 2009
Posts: 171
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

Joined: Oct 27, 2005
Posts: 19417

13

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.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6