Java, calculating complexity

64 views Asked by At

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

0

There are 0 answers