Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Is this an In-place algo?

naved momin
Ranch Hand
Posts: 692

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: 12234
36
• 1
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: 42968
73
• 1
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
• 1
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: 12234
36
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).