How to determine the time complexity of a recursive function that has a loop enclosed in it?

Question

I am trying to solve LeetCode problem 143. Reorder List:

You are given the head of a singly linked-list. The list can be represented as:

L₀ → L₁ → … → L_{n − 1} → L_n

Reorder the list to be on the following form:

L₀ → L_n → L₁ → L_{n − 1} → L₂ → L_{n − 2} → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

This is my attempt at it:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return; 
        }

        ListNode n1 = head;
        ListNode temp = null;

        while (n1.next.next != null) {
            n1 = n1.next;
        }

        temp = n1.next;
        n1.next = null;
        temp.next = head.next;
        head.next = temp;

        reorderList(temp.next);
    }
}

I'm unable to come up with concrete reasoning for the time complexity of my code. My brain says O(n^2) but I just can't justify the why. How can the time complexity be derived?

Please do not post images of code meta.stackoverflow.com/questions/285551/… — n. m. could be an AI
– n. m. could be an AI, Commented Mar 25, 2024 at 4:52

trincot · Accepted Answer · 2024-03-25 09:13:34Z

my brain says O(n^2) but i just can't justify the why.

Yes, it is O(𝑛²). One execution of reorderList -- excluding the recursive call -- will visit all the nodes in the list in the while loop. So if at that moment there are 𝑘 nodes in the list, this will be O(𝑘). The recursive call is made with a list that has 𝑘−2 elements (since head and temp are "behind" the reference that is passed to the recursive call). This means we have a number of visits that progresses as follows:

𝑛 + 𝑛−2 + 𝑛−4 + ... + (1 or 2)

This is about the double of the 𝑛/2 triangular number, which is O(𝑛/2(𝑛/2+1)) = O(𝑛²).

Improving the time complexity

It is possible to solve this problem with O(𝑛) time complexity. Here are some spoiler hints to get an idea how to approach it:

Hint 1:

Could you manipulate the list so that it becomes easier to also traverse the list from its current last node backwards?

Hint 2:

What is the time complexity to reverse a linked list?

Hint 3:

Would it help to split the list into two lists?

Spoiler O(𝑛) solution:

class Solution { public ListNode getMiddle(ListNode head) { ListNode fast = head.next; while (fast != null && fast.next != null) { head = head.next; fast = fast.next.next; } return head; } public ListNode splitAfter(ListNode newTail) { ListNode head = newTail.next; newTail.next = null; return head; } public ListNode reverse(ListNode head) { ListNode prev = null; while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; } public void zip(ListNode head1, ListNode head2) { if (head1 == null) return; ListNode head = head1; ListNode tail = head1; while (head1 != null && head2 != null) { head1 = head1.next; tail = tail.next = head2; head2 = head2.next; tail = tail.next = head1; } } public void reorderList(ListNode head) { if (head != null) { zip(head, reverse(splitAfter(getMiddle(head)))); } } }

Collectives™ on Stack Overflow

How to determine the time complexity of a recursive function that has a loop enclosed in it?

1 Answer 1

Improving the time complexity

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Improving the time complexity

Comments

Your Answer

Sign up or log in

Post as a guest

Related