1

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?

  • What language is this? how is variable target visible to the inside function? – Degen Sharew Apr 5 '16 at 9:35
  • It is Swift. I guessed it should be clear enough to be considered almost as pseudocode. – Mike M Apr 5 '16 at 10:13
4

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.

|improve this answer|||||
  • Wouldn't the complexity be independent of array size but be constant time? When the target is hit, it's hit. – Pieter B Apr 5 '16 at 9:03
  • 2
    So what? When an array is sorted, it's sorted - that doesn't make the sort constant time. – Useless Apr 5 '16 at 9:15
  • @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 Apr 5 '16 at 10:14
  • @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? – Mike M Apr 5 '16 at 10:20
  • @MikeM If you're looking for general info on the theory of algorithm analysis, see this question and its links on CS.SE. – DylanSp Apr 5 '16 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.