hi guyz... an algorithmic problem

[ayan_2587]

hi frndz...
here's a very small doubt that's been lingering for a while...

what is the meaning of finding an algorithm for a certain problem in constant space??
i dont understand the meaning of constant space, does it mean that no temporary variable can be created?

for ex:here's a question...

given an array- arr[6]={1,2,3,4,5,6}, i want to rotate the array from index k=3 in such a manner that it becomes-- arr[6]={3,4,5,6,1,2}

now this has to be done in constant space & time complexity of O(n)
so kindly reply...
Thanx..

[C_ntua]

Complexity: In general, is how much time the algorithm will need to be executed. If there is an iteration (like a for-loop) then if you need T time for each iteration you will tottaly need N*T time, if N are the iterations. If T is more or less constant, then the time needed for the program to execute will depend on N.
We say it has a O(N) complexity, it depends on N (since T is more or less constant). If it needed N^2*T time, it would have a O(N^2) complexity. The O() means maximum time needed, taking the worst case scenario.

So in your case, the steps need to be maximum n, where n is the number of elements in the array I guess.

Constant space I believe it means that it usess a specific number of space (memory) that doesn't increase. It is the same from the beginning.

Examples
If an algorithm needs S space for every element, thus S*N space (memory), then by giving a big N you will run out of memory. A constant space program doesn't have that problem.
In the same manner, if a program needs T time to execute, where T more or less constant, then whatever the input (the N number) the program will run. It has a complexity of O(1). If it needs N^2*T time to execute then for a large N it might take forever. In that case it has a complexity of O(N^2).

I believe the general idea is correct as I described (might be wrong). But I can tell you know that there are better explanations with more accurate wordings.

[iMalc]

Just in case this is any clearer:

Constant space means that you have to perform the rotation without using an extra array. You only have a fixed amount of extra space.

O(n) time complexity means that if it takes "t" amount of time for a rotation in an array of "n" items then it should take approximately 2*t time for a rotation in an array of 2*n items.

It just so happens that I have already written such an algorithm and it's sitting here in front of me right now. It's roughly 20 lines of code long.
There is also a simpler but less efficient way also which involves 3 sequence reversals, and it still operates under the same constraints above.