CODEWITHSUNDEEP
algorithmrecursionrecurrence
loremIpsum1771
loremIpsum1771

Reputation: 2527

What is the difference between these two recursive approaches

I have two versions of the same algorithm which recursively find the minimum element in a linked list. One algorithm first checks whether the end of the list has been reached and if so, returns that element then checks to see whether the current element (head of the list) is less then the current min from the recursive call. If the current element is greater, the current min (found by the recursive call) is returned.

The other algorithm does something only slightly different in that, after the check for the base case, it stores the recursive call in a temp variable and then uses temp to do the comparison with the current list element.

I found the recurrence for the first approach to be:

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

(which I'm not entirely sure about)

What I can't figure out is what would be the difference in the recurrence for the second algorithm as they seem to be doing the same thing. Does the recursive call being stored in the temp variable add extra work for the recurrence?

The pseudocode for both algorithms is below:

First approach

function min_list_1(L) // L is a non-empty list of numbers
    if has_only_one_element(L): return L.head
    if L.head < min_list_1(L.next): return L.head
    else:
        return min_list_1(L.next)

Second approach

function min_list_2(L) // L is a non-empty list of numbers
    if has_only_one_element(L): return L.head
    temp = min_list_2(L.next)
    if L.head < temp: return L.head
    else:
        return temp

Upvotes: 1

Views: 129

Answers (2)

shole
shole

Reputation: 4084

On top of loremIpsum1771's answer, I give you a simple analogy here:

for(int i=0; i< strlen(s); i++){
     ...
}
     
     
     vs
     
for(int i=0, len=strlen(s); i<len; i++){
     ...
}

Which one is faster and why?

The first one is much slower and the reason is exactly the same with your OP, you call something every time / many times when you can indeed precompute once

Upvotes: 1

Prune
Prune

Reputation: 77837

The first one will make the recursive call twice for most cases (when L.head isn't the smallest found): once to evaluate the condition, and a second time to return the new value. This causes a 2^n complexity. Using temp keeps it linear.

Upvotes: 4

Related Questions