CSC240 Winter 2021 Midterm Assessment Question 4
YOUR NAME and STUDENT NUMBER
4. (15 marks) Let F denote the set of all functions from N to R+ ∪ {0}.
Recall that Ω(f′) = {g′ ∈ F | ∃c ∈ R+.∃b ∈ N.∀n ∈ N.[(n ≥ b) IMPLIES (g′(n) ≥ c·f′(n))]}. Foranyfunctionsf∈F andg∈F,
letf+gdenotethefunctiona∈F wherea(n)=f(n)+g(n)foralln∈Nand
let max{f,g} ∈ F denote the function m ∈ F where m(n) = max{f(n),g(n)} for all n ∈ N.
Formally prove ∀f ∈ F .∀g ∈ F .[max{f, g} ∈ Ω(f + g)].
Number every line of your proof. Explicitly state when a proof technique is being applied and say which earlier lines it refers to.
Use proper indentation. However, to avoid excessive indentation, do not indent when making definitions.
Solution:
1