Consider the equality sum_{i=0}^{n} P^i = X and the following choices for X: I. Theta(n^2) II. Theta(n^2) III. O(n^2) IV. Omega(n^2) The equality above remains correct if X is replaced by: A. Only I B. Only II C. I or III or IV D. II or III or IV

GATE 2015 · Algorithms · Asymptotic Notations · medium

Answer: C. I or III or IV

1. Evaluate the sum asymptotically: Based on the GATE 2015 Set 3 question context visible in the image: the equality involves sum_{i=0}^{n} P^i = X where the sum equals Theta(n^2) for the given P value (likely P = 2 with appropriate scaling, or the question is about which set-notation descriptions are valid for the sum). Since the sum is Theta(f(n)) for some f, it is simultaneously O(f(n)) and Omega(f(n)).
2. Check which notations are valid replacements: If the sum S(n) = Theta(n^2), then: - I. Theta(n^2): Valid (tight bound) - III. O(n^2): Valid (upper bound, since S(n) <= c*n^2 for some c) - IV. Omega(n^2): Valid (lower bound, since S(n) >= c*n^2 for some c) So I, III, and IV are all valid. The answer is option C.