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 {

            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? Apr 5, 2016 at 9:35
  • It is Swift. I guessed it should be clear enough to be considered almost as pseudocode.
    – Mike M
    Apr 5, 2016 at 10:13

1 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.

  • 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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