# Solving a recurrence relation with two variables

I have this function which traverses each node of a left child-right sibling binary tree once and I want to solve the recurrence relation of the function.

First of all I think the relation looks like this:
T(n) = 1+m[4+T(n-m)] = 1+4m+mT(n-m)

Where m is the number of nodes on a level and n the total amount of nodes in the tree.

Is this correct? And how could I solve this recurrence relation with two variables?

void maxWidth(Node node, int height, vector<int> &width){
if(node==nullptr){
return;
}
while(node!=nullptr){
if(width.size()==height){
width.push_back(0);
}
if(width.size()>height){
width[height]=width[height]+1;
}
if(node->left_child!=nullptr){
maxWidth(node->left_child,height+1,width);
}
node=node->right_sib;
}
}


If you insist on solving a recurrence formula, you might want to compute $$T$$ based on the height of the tree first. Computing $$T$$ based on the number of nodes is much more complicated, and the $$T(n-m)$$ there is not correct - it needs to be $$T(n-\sum_{i=1}^m{k_i})$$ where $$k_i$$ is the size of the sub-tree which is rooted in the $$i$$'th child.

Otherwise (which is what I recommend doing), just notice that you will visit each node at most once. In each visit you will pay no more than $$O(1)$$ before each recursive call, and hence this algorithm will total to be $$O(n)$$.

However the above reasoning will need to be formalized if you want to keep it as a proof. That is, you will have to prove that indeed you will not visit each node more than once.

• I knew it was O(n) but I didn't know how to prove it, thanks for pointing out that T(n-m) was wrong in the formula Commented Dec 14, 2021 at 11:43
• If you would have kept it, the result would have been enormous, something like $\Omega(m^{\frac{n}{m}})$ Commented Dec 14, 2021 at 12:16
• how would you compute T using the height of the tree? Commented Dec 14, 2021 at 13:54
• Assuming the tree is balanced, $T(h)=O(m)+mT(h-1)$. If I'm not mistaken, solving this yields $T(h)=O(\sum_{i=1}^h m^i)=O(\sum_{i=1}^\log_m(n) m^i)=O(m^{\log_m(n)})=O(n)$ Commented Dec 14, 2021 at 16:36