Answered You can hire a professional tutor to get the answer.

QUESTION

What is the complexity of the following recurrence relation?

What is the complexity of the following recurrence relation? Show the details of your analysis.

T(1) = 1

T(n) = 2*T(n-1) + 1 

Hello I am trying to understand recurrence relations for a midterm coming up. I am not too sure how to solve the complexity.

What I have so far,

T(2) = 2 * T(2-1) +1 = 3

T(3) = 2 * T(2) +1 = 5

T(4) = 2* T(3) +1 = 7

T(5) = 2 * T(4) +1 = 9

since increase is directly proportional to n is this an O(n) complexity?

Show more
LEARN MORE EFFECTIVELY AND GET BETTER GRADES!
Ask a Question