Meaning of "constant space complexity"


  • 4
    M

    What does it mean? No extra space or O(1) extra space?
    What if using recursion, does the stack count as constant space?


  • 25
    S

    Constant space means that the amount of space that your algorithm uses is independent of the input parameters. Say you are given an array of size n. If the amount of space your algorithm uses scales with n, then it's not constant. If your algorithm always uses a fixed amount of space (5 variables, an array of fixed size: 100, 300, 5000, etc..), you are golden.


  • 8
    P

    constant space just means the memory you use does not depends on the size of the input.

    When you use recursion, the stack also counted.


  • 0
    Y

    but it seems the system cannot judge whether your space complexity if constant or not, I used merge_sort, although it requires O(n) space, but it passed.


  • 0
    P

    There is no way for the judge to tell if you are using constant space.


Log in to reply
 

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