hi guyz... an algorithmic problem

This is a discussion on hi guyz... an algorithmic problem within the C++ Programming forums, part of the General Programming Boards category; Code: hi frndz... here's a very small doubt that's been lingering for a while... what is the meaning of finding ...

  1. #1
    Registered User
    Join Date
    Oct 2009
    Posts
    11

    Question hi guyz... an algorithmic problem

    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..

  2. #2
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    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.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21