Complexity of recursive calls

Question

my brain is a little stuck as I am trying to compile an example for my blog. I am presenting an algorithm that draws a number from an array, adds it to a sum and calls itself recursively.

func solve(coins: Array<Int>, target: Int) -> Int {
 func _solve(coins: Array<Int>, current: Int) -> Int {
 var candidates = coins
 var crt = current
 while candidates.count > 0 {
 // pop() removes the element at the head and returns it
 let rdm: Int = candidates.pop() 
 if (current + rdm) > target {
 continue
 }
 crt = _solve(candidates, current: current + rdm)
 if crt == target {
 return crt
 }
 }
 return crt
 }
 return _solve(coins, current: 0)
}

What this algorithm is doing is, given a set of coins, try to approach a given target as close as possible.

What is the complexity of this algorithm?

• Degen Sharew: What language is this? how is variable target visible to the inside function?
• Mike M: It is Swift. I guessed it should be clear enough to be considered almost as pseudocode.

Answer 1

It doesn't matter that you pick the next coin randomly rather than systematically. You're still potentially trying out all subsets of a multiset of size N, so it may take as many as 2^N tries, and that's your (upper bound) complexity.

• Pieter B: Wouldn't the complexity be independent of array size but be constant time? When the target is hit, it's hit.
• Useless: So what? When an array is sorted, it's sorted - that doesn't make the sort constant time.
• Mike M: @Kilian Foth You are right. It does not matter that it is random. I updated the question to simplify by removing the random function.
• Mike M: @Kilian Foth Apart from that, thank you for the answer, could you please update it with a link to some theory as I am trying to wrap my head around it a little bit better?
• DylanSp: @MikeM If you're looking for general info on the theory of algorithm analysis, see this question and its links on CS.SE.