Which of the following can be recurrence relation(s) corresponding to an algorithm with time complex

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2026 GATE-CS Algorithm paper.

Q: How can I prepare for GATE-CS Algorithm?

To prepare for GATE-CS Algorithm, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2026 question covers Recurrence Relations and Master Theorem topic.

Q: What is the difficulty level of this question?

This GATE-CS 2026 Algorithm question has a medium difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity Theta(n)?

Accepted Answer

Correct Answer: (A) and (B)Concept -- Solving Recurrences (Master Theorem and Substitution): • A: T(n) = T(n-1) + 1 → T(n) = 1 + (n-1) = n → Θ(n).• B: T(n) = 2T(n/2) + 1. Master Theorem: a=2, b=2, f(n)=1. n^(log_b a)= n^1 = n. f(n)=1 = O(n^(1-ε)) for ε• C: T(n) = 2T(n/2) + n. Master Theorem: f(n)=n = Θ(n^1 log^0 n) → Case 2 → T(n) = Θ(n log n).• D: T(n) = T(n-1) + n → T(n) = n + (n-1) + ... + 1 = n(n+1)/2 = Θ(n^2).Why other options are incorrect: • C gives Θ(n log n), not Θ(n).• D gives Θ(n^2), not Θ(n).Note: The Master Theorem provides a direct way to solve recurrences of the form T(n) = aT(n/b) + f(n). For linear recurrences, telescoping or induction works. An algorithm that does constant work per element (like traversing an array) yields Θ(n).

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity Theta(n)?

Master GATE-CS with Our Test Series

More Questions from Recurrence Relations and Master Theorem

Frequently Asked Questions

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity Theta(n)?

Master GATE-CS with Our Test Series

More Questions from Recurrence Relations and Master Theorem

Frequently Asked Questions