递归方法的Big-O和Big-Omega

Question

我的任务是尝试找到给定Java方法的big-O和big-Omega，但不知道如何查找。我知道big-O给出了上界，big-Omega给出了下限，但是当我看一个程序时，我如何准确地弄清楚这一点，更不用说递归程序了？提前谢谢你，这对我的学习有很大的帮助。

public static boolean goal(int i, int n){
    if(n == 0){
        if( i == 91) {
            System.out.println("i = " + i +", DONE!!!");
            return true;
        }
        else {
            return false;
        }

    }
    else if(i % 2 == 1){
        if(goal(i + 53,n - 1))
        {
            System.out.println("i = "+ i + ", step # " + n);
            return true;
        }
        else
            return false;
    }
    else {
       if( goal(i + 53,n - 1) || goal(i / 2,n - 1))
       {
            System.out.println("i = "+ i +", step # " + n);
            return true;
       }
       else
            return false;
    }
}

Answer 1

每次递归迭代，当N减1时，递归停止，在最好的情况下，i总是奇数，所以你进入第一个分支，所以这个算法的下界是O(N)

上限是最坏的情况，是您的最后一个else分支，此时您可以调用goal两次，因此上限将是O(2^N)