• Post Reply Bookmark Topic Watch Topic
  • New Topic

string reverse O(N) or O(N/2)  RSS feed

 
Chandra shekar M
Ranch Hand
Posts: 171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

i am trying to reverse a string the code is below. in the //1 it is simple reverse and in //2 i have used two indexes for reverse.


Is it really true that first one is O(N) and //2 is O(N/2). I think it is not possible to reduce the time complexity by O(N/2) for strings.
No matter we use; one or two indexes we have to visit each element; we can tell it is O(N/2) only when we really don't visit remaining half elements.

I think we cant reduce the string reverse to O(N/2)? Please correct me if i am wrong.

Thanks
Chandrashekar
 
Ulf Dittmer
Rancher
Posts: 42972
73
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Note that there is no O(N/2) - it is linear complexity, and asymptotically the same as O(N). In this particular case, performance is probably improved much more by using a StringBuilder instead of string concatenation.
 
Chandra shekar M
Ranch Hand
Posts: 171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

In java String is stored as a char array; in java size of the array is predetermined and stored in head so getting the size of the array or string will be O(1).
and however string reverse will be O(N) it cant be less than this; as you will end up visiting each element when reversing.

Thanks
Chandra
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Regardless of how you store the String every character has to be considered to reverse the String, so regardless of whether it is in an array or a List, the best you are going to get is O(n)


Hunter
 
Vijay Kumar
Ranch Hand
Posts: 260
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Chandra shekar M wrote:Hi,

In java String is stored as a char array; in java size of the array is predetermined and stored in head so getting the size of the array or string will be O(1).
and however string reverse will be O(N) it cant be less than this; as you will end up visiting each element when reversing.

Thanks
Chandra


I doubt, why do I need to visit on each element on string? What about below code. I know there is no O(N/2), as Ulf said its linear complexity, but in this case it is.

 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Vijay Kumar wrote:

I doubt, why do I need to visit on each element on string? What about below code. I know there is no O(N/2), as Ulf said its linear complexity, but in this case it is.



Just because you don't iterate from 0 to N doesn't mean that you don't operate on every element from 0 to N. In the code above you perform two operations per iteration of your for loop, which still comes out to be O(n). So regardless of how many operations you perform in your loop, you still touch N elements.

Also, this thread is 3 years old; you probably shouldn't post on it.

Hunter
 
Vijay Kumar
Ranch Hand
Posts: 260
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Hunter,

I did post because I had an doubt and now its clear as you said
So regardless of how many operations you perform in your loop, you still touch N elements.



Thanks,
Vijay
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hunter McMillen wrote:Just because you don't iterate from 0 to N doesn't mean that you don't operate on every element from 0 to N.

But, as Ulf pointed out, that's not the major reason that an algorithm is O(n).

The O notation is used mainly as a guide to behaviour; specifically, as to how it's likely to change with changes in the amount of input. It should also be pointed out that it is not necessarily a good guide as to how long something will run, because 'O' is generally not defined.
Most often, the only things you're interested in are whether it's O(n), O(log n) or O(1).

I know this because I got it wrong...a while ago, it has to be said.

Also, this thread is 3 years old; you probably shouldn't post on it.

Now that is a good point; which I've unfortunately just broken myself.

Winston
 
Campbell Ritchie
Marshal
Posts: 56553
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
We used to worry a lot about old threads, but have changed our policy in the last year or two.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!