大哦表示法下面语句的运行时间是多少？

Question

public int foo (int x , int k) { 
    if (x <= k) 
     return 1; 
    else 
     return foo (x/k , k) + 1; 
} 

从我的理解，这应该等于条件的运行时间+较大的if/else语句的运行时间。

但是，我无法确定语句“return foo（x/k，k）+ 1”的正确运行时间。这会保持不变吗？ x和k的增加似乎对运行时间没有影响，因为它们之间的比率对结果很重要。

任何清晰度将不胜感激。谢谢！

Answer 1

递归调用每次将x除以k，所以k> = 2的复杂度为O(logk(x))-以k为底的x的对数。

对于k < 2它可能不会终止（实际上，它将耗尽内存或除以零）。