大哦表示法下面語句的運行時間是多少？

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它可能不會終止（實際上，它將耗盡內存或除以零）。