Question

Consider two algorithms A₁ and A₂ that have the running times T₁(n) and T₂(n), respectively.

T₁(n) = n³ + 3n    and T₂(n) = 50n².    

Use the definition of Ω() to show that T₁(n) € Ω(T₂(n))   

Answer 1

f(n) = Omega(g(n)) means there are positive constants c and n0, such that f(n) >= cg(n) for all n ≥ n0

n^3 + 3n = Omega(50n^2)

=>  n^3 + 3n >= c50n^2
Let's assume c = 1
=>  n^3 + 3n >= 50n^2
for n >= 50, n^3 + 3n >= 50n^2

so, n^3 + 3n = Omega(50n^2) for c = 1 and n0 = 50