Java Complexity – Time and Space Complexities of a Recursive Method to Reverse a Singly Linked List

complexityjavalinked listrecursion

What are the Time and Space complexities of this Java method that reverses a singly linked list (of length n)?

I'm more interested in knowing the reasoning behind the space complexity. Let me know if you'd like me to provide LinkedListNodeSingly and a convenience applet.

I believe both space and time complexities here are O(n). Time is O(n) since we go to the tail and work backwards through each of the n nodes. I'm unsure if space is O(n) because even though we create new_head for each frame, we happen to point it to an existing node (starting in the base case) and just pass that up. So, though we create n references, they all point to the same location which holds one value. So, is space O(1) even in the case where we perform LinkedListNodeSingly new_head = null; and 'return new_head'?

/**
 * Inspired by: http://www.programmerinterview.com/index.php/data-structures/reverse-a-linked-list/
 * 
 * Time: O(n), at least I think so, since it is recursive, going through each node once for list of size n
 * Space: O(1), if we don't use a return val, but since we do, each frame would create new_head once, for O(n)
 */
public static LinkedListNodeSingly reverseUsingRecursion(LinkedListNodeSingly node) {
    if(node == null)
        return null;

    LinkedListNodeSingly new_head = null;

    //base case, where we swap the head (very first node) with the tail (very last node)
    if(node.next == null) {
        new_head = node; //node is tail here
        return new_head; //don't need a return overall, really
    }

    //don't need a return overall, really
    new_head = reverseUsingRecursion(node.next);

    /* This next line is key.  It is better understood with an example. 
     * For list 1 2 3 4, we refer to each node by the data, e.g.: node 4 is the last (tail) node.
     * Going over the call stack:
     *  1. base case reached after 4th call to reverseUsingRecursion: return new_head == node 4 
     *  2. returning from base case, we're at node 3's frame: 
     *      2.1 We want node 4 to point back to node 3.
     *          Since node3.next == 4, node3.next.next = node3 sets node4.next to node3
     *      2.2 Since we want node3 to no longer to point to node4, we do node3.next = null.
     *          This breaks the previous direction of the singly list list between these two nodes.
     *          Q: Would we swap here if we were reversing a doubly linked list?
     *      2.3 We return the new head, node 4, all the way up to the first frame (to the first call to reverseUsingRecursion)
     *      2.4 At each return, we restore the frame for the previous node (e.g., point node3 to node2, after pointing node4 to node3, etc...)
     */    
    node.next.next = node;
    node.next = null;

    return new_head;
}

Best Answer

Your code doesn't allocate any objects, nevertheless it has O(n) space complexity. Whenever you call your method, the implementation will set up a call stack frame. At the least, this includes the return address, but in this case you will also need stack space for the parameters and any local variables. Even if a variable points only to null or to existing objects, we need some space to hold the pointer itself.

This is completely language independent, and it is not possible to recurse without using a bit of memory to remember where you should continue once you're finished (the one exception is a “tail call”, which is not present in your example, and which Java does not currently optimize away).

Let's look at this simplified example:

void countUpTo(int n) {
   if (n > 0)
       countUpTo(n - 1);
   System.out.println(n);
}

Obviously there are no allocations. Nevertheless, we are dealing with O(n) space complexity. Let's execute countUpTo(5):

  • countUpTo(5)
    • countUpTo(4)
      • countUpTo(3)
        • countUpTo(2)
          • countUpTo(1)
            • countUpTo(0)
              • println(0)
            • println(1)
          • println(2)
        • println(3)
      • println(4)
    • println(5)
Each level needs to remember to which outer level it must return. So when we are at countUpTo(3), we have to remember the following three levels:

  • main
  • countUpTo(5)
  • countUpTo(4)

Therefore, after println(3), we return to the countUpTo(4) context, which executes println(4) and then continues with the countUpTo(5) context.

When we are at countUpTo(0), we have to remember the following five levels:

  • main
  • countUpTo(5)
  • countUpTo(4)
  • countUpTo(3)
  • countUpTo(2)
  • countUpTo(1)

And remembering this stack needs space.

So when a function has a recursion depth of n, we can immediately say that it must at least have a space and time complexity of O(n).

Related Topic