What is the time complexity of recursive function?

Question

I have a recursive function. And i’m looking for what is the time complexity ? Here is the function

 public static int f7(int N){
         if (N==1) return 0;
         return 1 + f7(N/2);
   }

Emily · Accepted Answer · 2019-11-17 17:41:06Z

2

First, we come up with a recurrence for this function:

T(1) = 1
T(n) = T(n/2) + 1

This is a recurrence that we can plug into the master theorem, which will give us Θ(log n) as an answer.

answered Nov 17, 2019 at 17:41

Emily

1,0961 gold badge12 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

score 1 · Accepted Answer · 2019-11-17 20:07:38Z

1

Assume that when N=1, the call takes a time units, and when N is a power of 2, it takes b time units, not counting the recursive call.

Then

T(1) = a
T(2^n) = T(2^(n-1)) + b.

This can be seen as an ordinary linear recurrence

S(0) = a
S(n) = S(n-1) + b = S(n-2) + 2b = … = S(0) + nb = a + nb,

or

T(N) = a + Lg(N) b

where Lg denotes the base-2 logarithm.

When N is not a power of 2, the time is the same as for the nearest inferior power of 2.

The exact formula for all N is

T(N) = a + [Lg(N)] b.

Brackets denote the floor function.

answered Nov 17, 2019 at 19:50

user1196549