Reversing a list is not considered "O(1) space"


  • 178
    W

    It is a common misunderstanding that the space complexity of a program is just how much the size of additional memory space being used besides input. An important prerequisite is neglected the above definition: the input has to be read-only. By definition, changing the input and change it back is not allowed (or the input size should be counted when doing so). Another way of determining the space complexity of a program is to simply look at how much space it has written to. Reversing a singly linked list requires writing to O(n) memory space, thus the space complexities for all "reverse-the-list"-based approaches are O(n), not O(1).

    Solving this problem in O(1) space is theoretically impossible due to two simple facts: (1) a program using O(1) space is computationally equivalent to a finite automata, or a regular expression checker; (2) the pumping lemma states that the set of palindrome strings does not form a regular set.

    Please change the incorrect problem statement.


  • 55

    Quote from that same page:

    It is one of the most well-studied complexity measures, because it corresponds so closely to an important real-world resource: the amount of physical computer memory needed to run a given program.

    And in the real world, we often can write over the input, especially if we restore it, and it does make a difference whether we use O(1) extra space or O(n) extra space. I think being interested in the extra space is a perfectly valid viewpoint. Just because you prefer a different definition, doesn't mean this one is wrong.

    all "reverse-the-list"-based approaches are O(n)

    That fails to distinguish between approaches using O(1) extra space and those using O(n) extra space (like collecting the values in an array and then checking that). In your view, those are equally good? That's just not right.

    All that said, I do understand that O(1) extra space and O(1) written space differ as well and I don't want to lump them together and pretend they're the same, either. And I thank you for pointing the issue out and for your explanations.

    the pumping lemma states that the set of palindrome strings does not form a regular set.

    No, it doesn't state that. It can be used to prove that, though.


  • 0
    C

    How about this program, do you think it uses constant space?

    # reverse in place
    def reverse(ls):
        for i in xrange(len(ls)//2):
            ls[i], ls[-(i+1)] = ls[-(i+1)], ls[i]
        return ls

  • 0
    W

    Thank you for your comment. You are using "extra space" in every place, but I was talking about "space complexity". My point is, the mathematical definition of space complexity assumes read-only input, but if you change to a different term, surely you can mean what you want to mean. "extra space" is a legit one, as well as "auxiliary storage" as commonly used in textbooks.


  • 1
    W

    Its space complexity is O(n), but it uses O(1) auxiliary storage.


  • 0
    This post is deleted!

  • 4

    You can claim that yours is the one and only definition all you want, but that doesn't make it so. It's perfectly valid to use a more realistic definition. Yes, we can use that "multi-string Turing machine with input and output" as the model, but we don't have to if we don't want to. Especially not on a website about coding interviews for real world coding jobs. Here I think the normal Turing machine is way more appropriate. And at the very least not flat out "incorrect".

    I also think it's way more appropriate in the real world. If I use some API function and I care about its space usage at all, maybe because I'm running out of memory and don't want a crash, then all I care about is the extra space. I don't care whether the function can do it without temporarily changing the input. All I care about is what it costs me. And I already paid for the space of the input, so the extra space is the "space" complexity that I'm interested in. Yes, I keep calling it "extra space" here, but that's just because we're talking about different "space" definitions here and so I need to call it something to make the distinction. Normally, I just say "space".

    Do you seriously insist that it's "incorrect" to say that the function

    is_palindrome(string):
        for i from 1 to len(string)/2:
            if string[i] != string[-i]:
                return False
        return True
    

    takes O(1) space? Then you must be living quite high up in the theoretical academics ivory tower.

    All that said, I might start saying "extra space" instead of "space" outside of here as well, for the benefit of extra clarity. But I vouch to still never call other people's perfectly legitimate "O(1) space" statement flat out "incorrect".


  • 1
    W

    You are accusing me of picking a definition I favor; I do not agree with that and I insist there is only one definition for space complexity. You claimed when space complexity is defined with a normal Turing machine, it is effectively equal to the amount of extra memory being used. Please cite one such definition.

    As for the is_palindrome function example, you actually raised a very good point. The answer is: the space complexity of this function is not O(1), but instead O(logn). Justification: if the list has n elements, storing variable i alone will take O(logn) bits. Practically we call it is O(1) because we assumed n will not be bigger than the max integer a machine word can represent. This is also a common misunderstanding of space complexity, but it is independent from what this post is about, so I did not mention it.


  • 3

    You claimed when space complexity is defined with a normal Turing machine, it is effectively equal to the amount of extra memory being used. Please cite one such definition.

    Sorry, I slipped there. I shouldn't have tried to put it in those terms. Thanks for the correction.

    I should have just stuck with my actual point, that people simply mean extra space when they say space. Because like I said, that's what we're interested in in practice, and that's the actual cost of calling the function. The input is already prepared, that cost is already paid! The word "space" has been around a lot longer than complexity theory and computers. When you see that word, you shouldn't automatically assume that people are talking about the space complexity you're thinking of. If you do, then you are picking a definition you favor. And I believe most people here neither mean that definition when they say space, nor do they understand it that way when they read that word.

    Or let me put it this way: You're talking about the space complexity of problems, or of problem+algorithm pairs. We here are talking about the space taken/allocated by our functions. So it's wrong to add the input size to that, since allocating that space already happened before our functions get called. That's not a cost produced by our functions.

    I myself occasionally point out to people that they shouldn't call their solutions "O(...) time" when that's really just the average, not the worst case, with the reasoning that "O(...) time" is commonly understood as worst case if not specified otherwise. I think that's what really matters, that we understand each other. What things are commonly understood as. You call it a "common misunderstanding" (of the space complexity you're thinking of). I call it a common understanding (that "space" refers to the space allocated by our solutions).

    As for the is_palindrome function example, you actually raised a very good point. The answer is: the space complexity of this function is not O(1), but instead O(logn). Justification: if the list has n elements, storing variable i alone will take O(logn) bits.

    Yes, I know.

    What I asked is whether you seriously insist that it's "incorrect" to say that that function takes O(1) space. Because using your definition, and to be consistent, you should.

    Practically we call it is O(1)

    "We"? So even you yourself would call it that? Then where do you draw the line?


  • 1
    L

    Learned a lot from this, especially "the space complexity of this(is_palindrome) function is not O(1), but instead O(logn)". This reminds me of my Introduction to Algorithm stuffs, which have been ignored a lot due to practicality. Missing the time in ivory tower.


  • 0
    R
    This post is deleted!

  • 0
    R

    reversing does not need O(n) space, you just change the ways nodes are connected, without getting more space, it is O(1) space


  • 2
    C

    It's definetely O(n) in time, but O(1) in space. Space complexity is not about memory access. It's about how much the amount of memory that I need to solve my problem grows according to the size of my input.


  • 10
    B

    I bet you are a CS PhD.


  • 3

    This is going to be my favorite post on leetcode! Very interesting conversation. :) Although I would be more interested to see wangmenghui respond to the comment.


  • 0
    W

    Wanna give you an Up Vote @brianbclan


  • 0
    T

    I dont know about Wangmenghui but StefanPochmann here is the famous speedcuber and he holds many records for cubing and he has invented this classic Pochmann and blindsolving methods !! One word Genius and no wonder he ranks 1 here in leetcode


  • 1
    L
    bool isPalindrome(ListNode* head) {
        if(!head)
            return true;
        ListNode *p = head;
        int count = 0, mid = 0;
        while(p) {
            ++count;
            p = p -> next;
        }
        ListNode *p1 = NULL, *p2 = head, *tmp;
        while(mid < (count)/2) {
            ++mid;
            tmp = p2 -> next;
            p2 -> next = p1;
            p1 = p2;
            p2 = tmp;
        }
        if(count % 2 != 0)
            p2 = p2 -> next;
        while(p1 && p2) {
            if(p1 -> val != p2 -> val)
                return false;
        
            p1 = p1 -> next;
            p2 = p2 -> next;
        }
        return true;        
    }

  • 0
    D

    I bookmarked the page. Thank you for such discussion


  • 1
    X

    It is not reasonable anyhow to consider writing a memory multiple times as using more memory. There is no root in this at all.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.