If an algorithm's time complexity is Θ(n), what does that imply?
2025
If an algorithm's time complexity is Θ(n), what does that imply?
- A.
Only lower bound is n
- B.
Only upper bound is n
- C.
Both upper and lower bounds are n
- D.
Time complexity cannot be determined
Attempted by 121 students.
Show answer & explanation
Correct answer: C
If an algorithm has a time complexity of Θ(n), it means the running time grows linearly with input size n. Theta notation represents a tight bound, meaning the function has both:
an upper bound of O(n), and
a lower bound of Ω(n).
Therefore, the algorithm’s growth rate is bounded by n from both above and below.