Time complexity difference in Linkedlist implementation (Iterative VS Recursive)?

Question

Does the time complexity change in these two implementation of getting the count of nodes in a Linkedlist ?

 private int getCountIterative() {

    Node start = head;
    int count = 0;
    while (start != null)
    {
        count++;
        start = start.next;
    }
    return count;
}


private int getCountRecursive(Node node) {
    if (node == null)
        return 0;
    return 1 + getCountRecursive(node.next);
}

score 8 · Answer 1 · answered Jan 10 '19 at 21:27

8

No, the time complexity won't change.

However the performance and overall run time will usually be worse for recursive solution because Java doesn't perform Tail Call Optimization.

answered Jan 10 '19 at 21:27

Karol Dowbecki

43,645
9
78
111

I am not sure that tail call optimization is possible here - the recursive call is not the last operation. One can rewrite the code to make it possible, though. Can an optimizer do that? – Jan 11 '19 at 11:57

score 4 · Answer 2 · edited Jun 20 '20 at 09:12

TL;DR: it's the same complexitiy

To calculate the complexity of an operation (like a search or sort algorithm - or your example, the count), you need to identify the dominating operation.

For searching and sorting, it's usually comparisons. What is your dominating operation? Let's assume it's node.next, the lookup of the next node.

Then, both approaches have O(n) operations - so it's the same complexity.

Please be aware that this time complexity is a simplification. There are factors ignored, like the overhead of function calls. So, it's the same complexity, but that doesn't necessarily tell you which version is faster.

Time complexity difference in Linkedlist implementation (Iterative VS Recursive)?

2 Answers2

TL;DR: it's the same complexitiy