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);
}

Answer 1

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.

Answer 2

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.