hi guyz... an algorithmic problem

ayan_2587 · 11-11-2009, 04:01 PM

Code:

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 · 11-11-2009, 04:43 PM

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 · 11-12-2009, 01:47 AM

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.

11-11-2009, 04:43 PM	#2
C_ntua Registered User Join Date: Jun 2008 Posts: 1,134	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 NT 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^2T 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 SN 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^2T 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.
C_ntua is offline

11-12-2009, 01:47 AM	#3
iMalc Algorithm Dissector Join Date: Dec 2005 Location: New Zealand Posts: 2,475	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 2t time for a rotation in an array of 2n 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. __________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger
iMalc is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Need help understanding a problem	dnguyen1022	C++ Programming	2	04-29-2009 04:21 PM
Memory problem with Borland C 3.1	AZ1699	C Programming	16	11-16-2007 11:22 AM
Someone having same problem with Code Block?	ofayto	C++ Programming	1	07-12-2007 08:38 AM
A question related to strcmp	meili100	C++ Programming	6	07-07-2007 02:51 PM
WS_POPUP, continuation of old problem	blurrymadness	Windows Programming	1	04-20-2007 06:54 PM