BIg-Oh for reversing LinkedList in Java

Question

Please advise what would be the Big-O in these two cases. I understand that the base case would be constant O(1), but am confused how to compute for the rest and the recursion.

Case #1

public ListNode reverse1(ListNode list) {
    if (list == null || list.next == null) {
        return list;
    }
    ListNode after = reverse(list.next);
    list.next.next = list;
    list.next = null;
    return after;
}

Case #2

public ListNode reverse2(ListNode list) {
    if (list == null || list.next == null) {
        return list;
    }
    ListNode after = reverse2(list.next);
    ListNode temp = after;
    while (temp.next != null) {
        temp = temp.next;
    }
    temp.next = list;
    list.next = null;
    return after;
}

Answer 1

In your first case the recursion gives:

T(n) = T(n-1) + c 

where T(n) is the overall steps for n nodes, in order to reverse n nodes you just reverse n-1 in T(n-1) and add the nth node by doing constant operations which cost c (constant value doesn't matter).

The above recursive relation is easy to see that leads to:

T(n) = T(n-1) + c = T(n-2) + 2c =...= nc = O(n)

In your second case the recursion gives:

T(n) = T(n-1) + n + c 

That's because in order to reverse n nodes you reverse n-1 in T(n-1) and you traverse the list in order to place the node at the end which cost n and constant operations which cost at most c (c doesn't matter).

The above recursive relation is easy to see that leads to:

T(n) = T(n-1) + n +c = T(n-2) + n + (n-1) + 2c =...= n(n-1)/2 +nc = O(n^2)