• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

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

 
Ranch Hand
Posts: 175
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Rancher
Posts: 43081
77
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 175
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Ranch Hand
Posts: 492
Firefox Browser VI Editor Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Ranch Hand
Posts: 260
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 VI Editor Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Marshal
Posts: 79475
379
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
reply
    Bookmark Topic Watch Topic
  • New Topic