如何计算递归运行时间 (java)

Question

我有这个函数可以从二叉树打印数字 如果 [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); 
}

1. 函数的运行时间是多少？

2. 函数的公式是什么？

例如：

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

Answer 1

你可以使用主定理来计算这个特定函数的运行时间复杂度。你可以在这里找到定理 Complexity of recursive algorithms