Multiple choice

Directions: Find the time complexities of the following question.

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

  1. O(n2)

  2. O(nlog3)

  3. O(2n)

  4. O(log n)
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

This is the classic exponential recurrence. Expanding: T(n) = 2T(n-1) + 1 = 2(2T(n-2) + 1) + 1 = 4T(n-2) + 3 = 8T(n-3) + 7 = ... = 2^n T(0) + (2^n - 1). The dominant term is 2^n, so T(n) = O(2^n). The n² option would apply to T(n)=T(n-1)+n, and n^log 3 is for divide-and-conquer recurrences.

Keep practicing — related questions