Win a copy of Murach's Python Programming this week in the Jython/Python forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Is this an In-place algo?  RSS feed

 
naved momin
Ranch Hand
Posts: 692
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Is this algo is an in-place, according to me yes, because tmp[] is consider as auxiliary space, so space complexity still remains O(1)
Do you agree with my answer if no please explain me too
thanks for your time and effort..!!

 
fred rosenberger
lowercase baba
Bartender
Posts: 12441
42
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
naved momin wrote:
Is this algo is an in-place, according to me yes, because tmp[] is consider as auxiliary space, so space complexity still remains O(1)
Do you agree with my answer if no please explain me too
thanks for your time and effort..!!


I think not, but I could be wrong. I thought that "in place" means you swap elements within whatever structure you have. Further. I think your space complexity is actually O(N). The longer the string is, the more additional memory you need.
 
Ulf Dittmer
Rancher
Posts: 42970
73
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I thought that "in place" means you swap elements within whatever structure you have.

+1

I think your space complexity is actually O(N).

+1
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was raised to understand that you could also have a small, constant amount of additional auxiliary space, and still be considered in-place. Like a temp variable. Now "small" may be a bit subjective, but the "constant" part is key. In this case, you're using a temp variable (fine) and assigning it a new array of length k.length() - not fine. The amount of extra space you're using is not a constant; it's O(N). Or O(k) in this case.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12441
42
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike Simmons wrote:I was raised to understand that you could also have a small, constant amount of additional auxiliary space, and still be considered in-place.

I guess that makes sense. If I have an int array of 10 elements, to do any swapping, I would need a int variable to hold the one while i swap (unless I do that fancy boolean trick, which I hate but know is an option).
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!