Question

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

T₁(n) = 5n² + 3n and T₂(n) = 500n.

1. (12 points) Use the definition of Ω() to show that T₁(n) Ω(T₂(n))
2. (3 points) Which algorithm should you use? A₁ or A₂? Justify

Answer 1

Given
T1(n) = 5n2 + 3n and T2(n) = 500n.

(12 points) Use the definition of Ω() to show that T1(n) Ω(T2(n))
T1(n) = 5n2 + 3n
T2(n) = 500n
Definition of Big-Omega:
f(n) = Ω (g(n)) means there are positive constants c and k, such that 0 ≤ cg(n) ≤ f(n) for all n ≥ k
5n2 + 3n >= 500n
where c is 1 and n>0 and g(n) = 500n
So, from the definition of Big-Omega we can say that f(n) = Ω(g(n))
So, T1(n) = Ω(T2(n))

(3 points) Which algorithm should you use? A1 or A2? Justify
Time complexity of A1 is O(n^2)
Time complexity of A2 is O(n)
A1 is quadratic time where as A2 as linear.
A2 is better than A1.
So, we use A2 for the best.