CODEWITHSUNDEEP
javaruntime
user2913922
user2913922

Reputation: 159

Similar recursive case, different run time?

The first one's run time is O(log n) which I know is the run time for most recursive cases. 

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); 
}

However, the second recursive case's run time is 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); 
}

Can anyone explain why? I would really appreciate that!

Upvotes: 0

Views: 62

Answers (1)

mojo
mojo

Reputation: 4142

The first function reduces n much quicker than the second. happy divides n by 2 until it gets below 100. silly subtracts 2 until it gets below 10.

happy is O(log n) because it takes log_2(n) steps until it gets down below 100, then at most 50 steps to get below 1.

silly is O(n) because it takes n/2 steps to get below 100, then at most 5 steps to get below 1.

Upvotes: 1

Related Questions