Report

Computer Sciences 1 GROWTH OF FUNCTIONS TUTORIAL 2 Computer Sciences 2 Objective * Describe growth of functions. * How we indicate running times of algorithms O ≈ ≤ Ω ≈ ≥ Θ ≈ = By using the definition of O-notation show that : n3 ≠ O(n2) Solution : 0 ≤ h(n) ≤ cg(n) 0 ≤ n3 ≤ cn2 0/n2 ≤ n3/n2 ≤ cn2/n2 0≤n≤c divides by n2 because n → ∞, no c exists where ∀ n ≥ n0 true By using the definition of Ω-notation show that : n ≠ Ω (n2) Solution : 0 ≤ cg(n) ≤ h(n) 0 ≤ cn2 ≤ n 0/n2 ≤ cn2/n2 ≤ n/n2 0 ≤ c ≤ 1/n Divide by n2 Θ-notation By using the definition of Θ-notation c1n2 ≤ n2/2-2n ≤ c2n2 with c1=1/2, c2=1/2 & n0=5 Θ-notation Solution : ½ (5)2 ≤ (5)2/2-2(5) ≤ ½ (5)2 25/2 ≤ 25/2- 10 ≤ 25/2 25/2 ≤ 25/2- 20/2 ≤ 25/2 25/2 ≤ 5/2 ≤ 25/2 Doesn't hold because 25/2 > 5/2 Conclusion * O-notation : _ O(g(n)) = { f (n) : there exist positive constants c and n0 such that 0 ≤ f (n) ≤ cg(n) for all n ≥ n0} . * Ω-notation _(g(n)) = { f (n) : there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f (n) for all n ≥ n0} . * Θ-notation _(g(n)) = { f (n) : there exist positive constants c1, c2, and n0 such that 0 ≤ c1g(n) ≤ f (n) ≤ c2g(n) for all n ≥ n0} .