類似的遞歸情況，不同的運行時間？

Question

第一個運行時間是O（log n），我知道這是大多數遞歸情況下的運行時間。

int happy (int n, int m) { 
    if (n < 10) return n; 
    else if (n < 100) 
     return happy (n - 2, m); 
    else 
     return happy (n/2, m); 
} 

然而，第二遞歸的情況下的運行時間爲O（n）

int silly(int n, int m) { 
    if (n < 1) return m; 
    else if (n < 10) 
    return silly(n/2, m); 
    else 
    return silly(n - 2, m); 
} 

任何人都可以解釋，爲什麼？我真的很感激！

Answer 1

第一個函數比第二個函數減少了n。 happy除以n 2，直到它得到低於100。silly減去 2，直到它得到低於10

happy是O（log n）的，因爲它需要log_2（n）的步驟，直到它得到下低於100，則在獲得最多50個步驟如下1.

silly是O（n），因爲它需要N/2步驟獲得低於100，則最多5個步驟來獲得低於1