Page 1 of 1
[15 marks] Proving Asymptotic Claims. Prove the following statements hold using the definition of Big-Oh: (a) [3 marks]
Posted: Sat May 14, 2022 2:40 pm
by answerhappygod
- 15 Marks Proving Asymptotic Claims Prove The Following Statements Hold Using The Definition Of Big Oh A 3 Marks 1 (49.73 KiB) Viewed 71 times
[15 marks] Proving Asymptotic Claims. Prove the following statements hold using the definition of Big-Oh: (a) [3 marks] 2022 is 0(1). (b) [3 marks) 3n3 + 2n is O(n). (c) [3 marks) sn) = 3 +6+9+ 12 + ... +3n is O(n?). (d) [3 marks] 2 log2 (n) + 2 is O(log2 (n)). Hint: Remember that logarithms of one base can be changed to a logarithm of another valid base, via the change of base formula. Perhaps simplify a bit further before selecting any constants. Make sure you pick ng large enough. (e) [3 marks) n + 7 is not (1), using the definition of Big-Oh (either its negation or via contradiction).