Activity $2$: Proving Big$-$O Functions

Learning Outcomes

By the end of this activity, the students should be able to:

Use Big$-$O notation formally to give expected case bounds on time complexity of algorithms.

Instructions

Prove the following:

$5n^4-37n^3+13n-4$ is $O(n^4)$

$\frac{n}{2}+7$ is $O(n)$

$2n^2+11n-20$ is $O(n^2)$

$3n+7$ is $O(n)$

$n^2+1000$ is $O(n^2)$