java - 为递归方法确定Big O

我试图弄清楚如何为递归方法确定Big O表示法。我意识到这可能与迭代方法相同，但是对此我不确定。

我写了这个简单的递归Java程序：

public RecursiveFunctions() {
recursiveFunction1(2);
}

// Meget simpel rekursiv metode der taeller en Integer ned
public void recursiveFunction1(int someInteger) {
    System.out.println("Tallet er nu : " + someInteger);
    someInteger = someInteger * 2;
    if (someInteger < 100) {
        recursiveFunction1(someInteger);
    }
}

我不确定，但是我猜这是O（n）还是O（1）表示法？
另外，O（n ^ 2）或O（log（n））包含什么？

最佳答案

根据您的观察方式，它是O（1），因为对于正输入它总是最多需要7次迭代，您可以说它将是O（lg n），因为所需的迭代次数将相对于lg改变输入的基数2或未定义，因为非肯定输入的计算永远不会完成。随便挑！