worst-case asymptotic time complexity of F# function

Question

I'm trying to figure out the worse case asymptotic time complexity of the following function:

let rec min = function
| [k] -> k
| k::ks -> if k <= min ks then k else min ks 

I know that it's not efficient, due to calling min twice in the 2nd pattern match. But how would you find the worse-case of this function?

Answer 1

As you noticed, the min function is

calling min twice in the 2nd pattern match

In the worst-case scenario (with the minimum at the end of the list), it's 2 calls for every element of the list, each again calling itself twice for the tail of the list, ...

So the complexity is O(2^n).

If you evaluate min ks once and use the value, the complexity will be O(n).

let rec min = function
    | [k] -> k
    | k::ks -> 
        let minTail = min ks
        if k <= minTail then k else minTail