Given the recurrence relation for the worst-case time complexity • T(n) = c,…
2025
Given the recurrence relation for the worst-case time complexity
• T(n) = c, when n = 1
• T(n) = T(n/2) + c, otherwise
Where c is a constant the recurrences solves to :
T(n) = c[1 + log2n]
What is the worst-case time complexity of this algorithm ?
- A.
Θ(n)
- B.
Θ(log n)
- C.
Θ(n log n)
- D.
Θ(1)
Attempted by 33 students.
Show answer & explanation
Correct answer: B
The recurrence T(n) = T(n/2) + c describes a process where the problem size halves each step with constant work. This creates a recursion tree of depth log base 2 of n. Summing the constant cost across all levels yields a total complexity proportional to log base 2 of n. Therefore, the worst-case time complexity is Theta(log n).