Use the definition of “big Oh” to prove that n3 + 2n2is O(n3)

Use the definition of “big Oh” to prove that n(n + 1) is not O(n)

Let f(n), g(n), and h(n) be non-negative functions such that f(n) is O(g(n)) and g(n) is O(h(n)). Use the definition of “big Oh” to prove that f(n) is O(h(n))

 

CS 2210a Data Structures and AlgorithmsAssignment 1 (20 marks)Due September 29 at 11:59 pm.You need to print and fll out an assignment submission Form. The Form can be downloaded Fromhttp://www.csd.uwo.ca/courses/CS2210a/submForm.pdf.You must staple the submission form at the front of your assignment, so the submissionform is the cover page.Drop your assignment in the CS2210 locker (located on the third ±oor oFthe Middlesex College Building, beside room MC300) by 11:59 pm on September 29.²or questions 1 and 3 proceed as Follows:1. ²irst explain what needs to be proven: “We need to fnd constantsc >0 andn0≥1 integersuch that...”.2. ²or question 3 use the defnition oF “big Oh” to explain what it means Forf(n) to beO(g(n))and Forg(n) to beO(h(n)).3. SimpliFy the above inequalities.4. Determine the values Forcandn0.²or question 2, iF you use a prooF by contradiction:•²irst give the claim that you will assume False and From which you will derive a contradiction.•PerForm steps 1 and 3 as above•Derive a contradiction.1. (3 marks) Use the defnition oF “big Oh” to prove thatn3+ 2n2isO(n3).2. (3 marks) Use the defnition oF “big Oh” to prove thatn(n+ 1) is notO(n).3. (3 marks) Letf(n),g(n), andh(n) be non-negative Functions such thatf(n) isO(g(n)) andg(n) isO(h(n)). Use the defnition oF “big Oh” to prove thatf(n) isO(h(n)).4. LetAbe an array storingninteger values. The goal is to design an algorithm that returnstrueiF every value stored inAappears at least twice in the array; the algorithm returnsfalseotherwise, i.e. iF there is at least one value that appears only once inA.²or example, For the Following arrayAthe algorithm must returntrueas values 1 and 6 appeartwice and value 3 appears three times; however For arrayBit must returnfalseas the value 3appears only once.36163130123456A277273012345B•(4 marks) Write pseudocode For an algorithm as described above.•Prove that your algorithm is correct:(a) (1 mark) Show that the algorithm terminates.(b) (2 marks) Show that the algorithm always produces the correct answer.•(1 mark) Explain what the worst case For the algorithm is.1

Attachments:

• 1494553997-asmt1.pdf