类似的递归情况，不同的运行时间

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。