A comprehensive solution set for analyzing algorithm performance. This download includes detailed proofs for asymptotic bounds (Big O, Theta, Omega) using limits and formal definitions, along with step-by-step derivations of time complexity $T(n)$ for nested loops using integral approximation and summation techniques.
1. (8 points) Give an example of a function f(n) such that:
• f(n) ∈ O(n
3
) but f(n) ̸∈ Θ(n
3
) and f(n) ∈ Ω(n
2
log2
(n)) but f(n) ̸∈ Θ(n
2
log2
(n)).
Justify your answer.
2. (8 points) Give an example of a function f(n) such that:
• f(n) ∈ O(n
0.5/ log2
(n)) but f(n) ̸∈ Θ(n
0.5/ log2
(n)) and f(n) ∈ Ω((log2 n)
2
) but f(n) ̸∈ Θ((log2 n)
2
).
Justify your answer.
3. (10 points) Prove that
4
p
7n9 − 12n7 + 5n5 + 3 ∈ Θ(n
4.5
)
using the definition of Θ as functions f(n) such that c1 · n
4.5 ≤ f(n) ≤ c2 · n
4.5
for constants c1, c2 > 0 and
all sufficiently large n.
Requirements:
• Give a rigorous proof that does not simply ignore lower-order terms.
• Clearly show how you handle the negative term −12n
7
.
• State your values of c1, c2, and n0.
4. (10 points) Prove that
6n
4
log2
(5n
3 + 3n
2 + 2n + 1) ∈ Θ(n
4
log3
(n))
using the definition of Θ.
Requirements:
• Give a rigorous proof that does not simply ignore lower-order terms.
1
• Use logarithm properties appropriately.
• State your values of c1, c2, and n0.
5. (8 points) Let f(n) = 2√
3 n
2
log4
(n
2
) and g(n) = 5√
n4 + n3.
Using limits, prove that f(n) ∈ Ω(g(n)) but f(n) ̸∈ Θ(g(n)).
Requirements:
• Compute limn→∞
f(n)
g(n)
explicitly.
• Show all algebraic simplifications.
• State what the limit value tells you about the asymptotic relationship.
6. (6 points) Determine the asymptotic bound (in Θ notation) for the following summation:
nX2
i=1
i
Show your work using the closed-form formula for arithmetic series.
