Q48: Solve recursive equation

Question #48: What will be the time complexity of the following recurrence relation?

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

 

Options:

1. O(log(n))
2. O(n)
3. O(nlog(n))
4. O(n²)

 

Solution:

We can expand the recurrence relation above as follows:

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

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

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

And so on..

Finally, the relation will look like this: (1+2+4+8+16+…+n/2) having totally log(n) terms, which after applying GP sum evaluates to ‘n’. Hence, the correct answer is option 2.