How to calculate Recursion runtime (java)

Question

i have this function that print numbers from Binary tree if the numbers in range [a,b]

public void print_in_range(Node root,int a, int b){ // print all num in [a,b] --> (a < b) 
    if(root == null)
        return;
        
    if(root.value >= a  && root.value <= b)
        System.out.print(root.value + ",");
    
        print_in_range(root.left, a, b);
        print_in_range(root.right, a, b); 
}

What is the runtime of the function?
what will be the formula of the function?

For example:

T(n) = 3T(n/4) + n --> T(n) = O(n)

But he asks about specific problems \ function

undertale
– undertale

2021-01-16 14:26:32 +00:00
Commented Jan 16, 2021 at 14:26 — undertale
– undertale, Commented Jan 16, 2021 at 14:26

Mohammed Faour · Accepted Answer · 2021-01-16 14:01:26Z

1

u can use the master theorem to calculate the run time complexity of this particular function. you can find the theorem here Complexity of recursive algorithms

answered Jan 16, 2021 at 14:01

Mohammed Faour

9787 silver badges12 bronze badges

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

2 Comments

daniel Over a year ago

yes, i know how to use the master theorem, but i dont know how to build the formula for this function. I think it is T(n) = 2T(n-1) + O(1) But I'm not sure

Mohammed Faour Over a year ago

I think this would be T(n) = 2T(n/2) + O(1), note that O(1) is same as O(n^0) so master theorem still applies. It is n/2 because for each iteration you will cut the tree in half (right and left) and it has a constant function "O(1)" because you are nly printing there is no calculations

Collectives™ on Stack Overflow

How to calculate Recursion runtime (java)

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related