1

I am trying to find the time complexity of the recursive function below. I've tried to draw the tree, but it is confusing because in the if condition the function is called once, and otherwise twice.

To give some context, the function is called on nodes of a tree. The task is to calculate the max rating of each node. The rule is that if you add some node to the rating you can't add it's children to the node, but if you don't add it than you can which children to add or don't.

Here is the function:

static int solve(Node node, boolean take) {     
    int result;
    if(take) {          
        result = node.rating;
        for(Node child : node.children) {
            result += solve(child, false);
        }
        return result;
    }

    result = 0;
    for(Node child : node.children) {
        result += Math.max(solve(child, true), solve(child, false));
    }
    return result;
}
josefk
  • 29
  • 1
  • 2
  • Regardless of actually calculating the time complexity of the algorithm - I highly suggest you use memoization in order to calculate `solve(child,false)` only once per tree node. As it is - you will perform multiple recursive calls of the solve method on the same tree nodes which is a complete waste IMHO. – Rann Lifshitz Jun 09 '18 at 16:16
  • After looking at: https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation - Assuming the tree has a depth of `n` and each tree node has on average `m` children (with the exception of the child-less leaf nodes which are the termination point of the recursion) my gut tells me you are dealing with O(m^3n) complexity currently - for each node from `m`, the average number of children per node, you will have 3 recursive activations of your method on the entire `n` depth of your tree - one for solve with take=true and two for solve with take=false. – Rann Lifshitz Jun 09 '18 at 16:27

0 Answers0