I am trying to calculate complexity of a recursion method inside another methos in a simple while loop.
I dont know how to asnwer this question, I think To just apply the answer O(N*Y) while Y stands for the tree on the recursion.
Tree recursion that gets the number of leafs that bigger Than x:
public static int bigger(BinaryNode<Integer> t, int x)
{
if(t==null)
{
return 0;
}
if (t.getValue()>x) {
return 1;
}
return bigger(t.getLeft(),x) + bigger(t.getRight(),x);
}
This is the Method I need to calculate the Complexity for(uses Bigger() in each iteration):
public static Stack<Item> bigInTree(BinaryNode<Integer> bt,Stack<Integer> s) {
Stack<Item> n = new Stack<>();
while (!s.isEmpty())
{
n.push(new Item(s.top(),bigger(bt,s.top())));
s.pop();
}
return n;
}
Is it O(N^2) or can i simply call it O(N*Y) (Y= number of leafs on t)
Let me know what you think