Calculate complexity in recursive algorithm with deep limit

Question

Good morning, I am studying algorithms and the way to calculate complexity when doing recursive calls, but I cannot find a reference on how a level limit in recursive calls can affect the complexity calculation. For instance this code:

   countFamilyMembers(int level,....,int count){
        if(noOperationCondition) { // for example no need to process this item because business rules like member already counted
            return count;
        } else if(level >= MAX_LEVEL) { // Level validation, we want just to look up to certain level
            return ++count //last level to see then no more recurrence.
        } else {
            for (...each memberRelatives...) {  //can be a database lookup for relatives to explore
                count = countFamilyMembers(++level,...,++count);
            }
            return count;
        }
    }

I think this is O(2^n) because the recursive call in the loop. However, I have two main questions: 1. What happens if the loop values is not related to the original input at all? can that be considered "n" as well? 2. The level validation is for sure cutting limiting the recursive calls, how do this affect the complexity calculation?

One approach is to try unrolling the recursion into a loop (looks pretty straightforward in this case). Then you can evaluate the complexity of the non-recursive algorithm, which is often easier to do. — PaulF
– PaulF, Commented Oct 21, 2016 at 20:15
What is n in terms of your original input parameters? Is MAX_LEVEL a constant? Is the fan-out (number of relatives from a given node) bounded, or another variable, or something else? These seriously affect the complexity. — Prune
– Prune, Commented Oct 21, 2016 at 21:01
n is related to the number of relatives of each person. MAX_LEVEL is a constant, I think this should decrease complexity a lot or at least write complexity in terms of it, I am not sure how yet. The number of relatives for a given node is not bounded, it can be any value like in real life. — Luis Felipe
– Luis Felipe, Commented Oct 21, 2016 at 22:24

Prune · Accepted Answer · 2016-10-21 23:28:09Z

0

Thanks for the clarifications. So we'll take n as some "best metric" on the number of relatives; this is also known as the "fan-out" in some paradigms.

Thus, you'll have 1 person at level 0, n at level 1, n^2 at level 2, and so on. A rough estimate of the return value ... and the number of operations (node visits, increments, etc.) is the sum of n^level for level ranging 0 to MAX_LEVEL. The dominant term is the highest exponent, n^MAX_LEVEL.

With the given information, I believe that's your answer: O(n^^MAX_LEVEL), a.k.a. polynomial time.

Note that, if you happen to be given a value for n, even an upper bound for n, then this becomes a constant, and the complexity is O(1).

answered Oct 21, 2016 at 23:28

Prune

78k14 gold badges63 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Luis Felipe Over a year ago

thank you very much! I really appreciate the simplicity of the answer in terms of levels, very well explained and clear! Could you please just elaborate on the last line about constant time? If n has a upper bound, wouldn't it still iterate n times, for each level, and then n again for each of the relatives?

Prune Over a year ago

Assume that MAX_LEVEL is 5 and n is limited to 10. You now have a strict upper bound of 10^5 + 10^4 + ... + 10^0 inspections. That's 111,111 inspections. Any constant bound gives you an O(1) complexity. Granted, it may complete in less time than that, but you've eliminated the parameters as an unconstrained factor of the running time. Yes, you can somewhat predict that shorter running time, by scaling with an actual value of n, but in complexity theory, that's simply "sub-constant time" details.

Collectives™ on Stack Overflow

Calculate complexity in recursive algorithm with deep limit

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related