Space complexity with stack (example: reverse linked list)


  • 0
    B

    I would like to learn how to calculate space complexity including the stack.

    Using this problem as an example: https://leetcode.com/articles/reverse-linked-list/

    The recursive Approach #2 solution is said to have a O(n) space complexity. My reasoning is that each "Listnode head" in the parameter takes O(1) space and there will O(n) recursive method calls. During each call the parameter is added to the stack, so a total of n calls * 1 space per parameter = O(n) space. However, the article says "The recursion could go up to n levels deep.". Does "level" just mean how many recursive calls there will be? And I thought this function always (instead of "can") goes to n levels deep.

    Also, does the type of recursion (tail vs. non-tail) affect the space/time complexity? Approach #2 seems to be tail, and I believe tail recursion is more efficient, but O(n) does not seem particularly space-efficient.

    Thanks!


  • 0

    You posted in the wrong category. Moving this to "General Discussion".


  • 0

    @bluecloud By the way could you post this comment here?
    https://discuss.leetcode.com/topic/28/reverse-linked-list

    I think it's more appropriate to answer your question there.


Log in to reply
 

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