GATE CS 1993 Q8.7 — Asymptotic Worst Case Time and Space Complexity

To find the asymptotic upper bound of the summation $\sum_{1 \le k \le n} O(n)$, we analyze the behavior of the sum:

$$\sum_{k=1}^{n} O(n) = \underbrace{O(n) + O(n) + \dots + O(n)}_{n \text{ times}}$$

Each term in the summation is bounded above by $c \cdot n$ for some positive constant $c$. Summing this $n$ times gives:

$$\sum_{k=1}^{n} O(n) \le \sum_{k=1}^{n} c \cdot n = c \cdot n^2 = O(n^2)$$

Now let's evaluate each option based on the properties of Big-O notation:

• Option B ($O(n^2)$): This is the tightest upper bound of the summation.
• Options D ($O(3n^2)$) and E ($O(1.5n^2)$): Constant factors inside the Big-O notation do not change the complexity class. Therefore, $O(3n^2) = O(n^2)$ and $O(1.5n^2) = O(n^2)$. Both are mathematically correct.
• Option C ($O(n^3)$): Since $n^2 \le n^3$ for all $n \ge 1$, any function that is $O(n^2)$ is also asymptotically bounded by $O(n^3)$. Thus, $O(n^3)$ is a valid (though looser) upper bound.

Hence, options B, C, D, and E are all correct.