Multiple choice

Directions: Find the time complexities of the following question.

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

  1. O(n2)

  2. O(nlog3)

  3. O(2n)

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

This recurrence adds approximately n at each of n steps (the constant c is negligible). Summing 1 + 2 + 3 + ... + n = n(n+1)/2 = O(n²). This is the formula for the sum of the first n integers. The O(n) option would require constant work per step like T(n)=T(n-1)+1, and O(2^n) would be for T(n)=2T(n-1)+c.

Keep practicing — related questions