A program consists of two parts that are executed sequentially. The size of the input is...

   

Transcribed Image Text:

A program consists of two parts that are executed sequentially. The size of the input is described by n. The first part has a time complexity that can be expressed as t₁(n) = 5n² + 16 and the second part has the time complexity t₂(n) = 6n3+n² + 18. Use only the definition of the big O notation, do not use any laws for the big O notation (unless you prove them as well). a) To which big O sets do t₁ and t₂ belong? b) To which big O set does the entire program belong? c) Prove that if f₁ = O(91) and f2 € O(92), then (fi + f2) O(max{91, 92}). A program consists of two parts that are executed sequentially. The size of the input is described by n. The first part has a time complexity that can be expressed as t₁(n) = 5n² + 16 and the second part has the time complexity t₂(n) = 6n3+n² + 18. Use only the definition of the big O notation, do not use any laws for the big O notation (unless you prove them as well). a) To which big O sets do t₁ and t₂ belong? b) To which big O set does the entire program belong? c) Prove that if f₁ = O(91) and f2 € O(92), then (fi + f2) O(max{91, 92}). A program consists of two parts that are executed sequentially. The size of the input is described by n. The first part has a time complexity that can be expressed as t₁(n) = 5n² + 16 and the second part has the time complexity t₂(n) = 6n3+n² + 18. Use only the definition of the big O notation, do not use any laws for the big O notation (unless you prove them as well). a) To which big O sets do t₁ and t₂ belong? b) To which big O set does the entire program belong? c) Prove that if f₁ = O(91) and f2 € O(92), then (fi + f2) O(max{91, 92}).

Answer rating: 100% (QA)

a To find the big O sets for tn 5n 16 and tn 6n n 18 we need to find functions gn and gn such that t... View the full answer