Answered You can hire a professional tutor to get the answer.
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?