Menu
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);
}
779
Strengths: Iteration can be used to repeatedly execute a set of statements without the overhead of function calls and without using stack memory. Iteration is faster and more efficient than recursion. It's easier to optimize iterative codes, and they generally have polynomial time complexity.
Recursion is when a statement in a function calls itself repeatedly. The iteration is when a loop repeatedly executes until the controlling condition becomes false.
Each insert operation should take O(1) time complexity.
The time complexity of recursion depends on two factors: 1) Total number of recursive calls 2) Time complexity of additional operations for each recursive call. So recursion tree is a diagram to represent the additional cost for each recursive call in terms of input size n.
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.
145
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.
38
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
