The sum is $[n(n+1)/2]^2$, hence Θ(n⁴). It is also O(n⁵), a looser upper bound, and Ω(n³), a looser lower bound. It is not Θ(n⁵) because its ratio to n⁵ tends to zero. Thus C.
More Asymptotic Analysis and Time/Space Complexity questions
GATE 2015 CS (CS3) Q37– Worst-case mergesort takes 30 seconds for input size 64. Which best approximates the…
GATE 2015 CS (CS3) Q41– L1≤pL2, L3≤pL2 and L2≤pL4. Which are guaranteed? I: L4∈P implies L2∈P. II: L1∈P or L3∈P…
GATE 2015 CS (CS3) Q64– For positive integer n, f(n)=n and g(n)=n1+ n. Which hold? I: f=O(g). II: f=Ω(g).
GATE 2021 CS (CS2) Q49– For constants a≥1,b>1, T(n)=aT(n/b)+f(n). Which general claim is correct, under the usual…
GATE 2026 CS (CS1) Q17– Consider the following recurrence relations: For all n > 1: T 1(n) = 4T 1(n/2) + T 2(n) T…
GATE 2026 CS (CS1) Q47– Let G(V, E) be a simple, undirected graph. A vertex cover of G is a subset V' V such that…