Let n $>0($usually n is the size of the input$)$ and let f $($n$)$ and g$($n$)$ be two

monotone and non$-$negative functions. We say that f $($n$)=$ O$($g$($n$))$ if there

exists a constant c and a constant n$0$ such that: f $($n$)<=$ cg$($n$),$n $>$ n$0.$

The exercise asks you to use the definition to prove the following:

$$ Let f $($n$)=100$n$2+10$n $+1000.$ Then f $($n$)=$ O$($n$2).$

$$ Let f $($n$)=100$n $+0\mathrm{.}001$n log n$.$ Then f $($n$)=$ O$($n log n$).$

$$ Let f $($n$)=50$n log n $+30$n$.$ Then f $($n$)=$ O$($n$3).$

Feel free to use standard properties or inequalities for the logarithm without

proof.

Ex$\mathrm{.}3$ Imagine you had an algorithm with runtime T $($n$)$ satisfying the recursion

T $($n$)=$ T $($n$/2)+1($and T $(1)=1).$ You have probably seen the binary search

algorithm that exactly obeys that recursion. Prove that T $($n$)=$ O$($log n$).$ Then,

imagine another algorithm with Q$($n$)=$ Q$($n$/2)+$ n $($and Q$(1)=1).$ Prove that

Q$($n$)=$ O$($n$)\mathrm{.}2$

Ex$\mathrm{.}4$ Describe an O$($n log n$)-$time algorithm that, given a set S of n integers

and another integer x$,$ determines whether or not there exist two elements in S

whose sum is exactly x$.$

Ex$\mathrm{.}5$ Follow the O$()$ definition & prove: Is $2$n$+2023=$ O$(2$n$)?$ Is $22$n $=$ O$(2$n$)?$

Ex$\mathrm{.}6$ Imagine you came up with an algorithm that depends on a parameter

k in $[1,$ n$]$ you can control. After calculations, the runtime ends up being

O$($nk $+$ n$2$

k $).$ What choice of k would you make for your algorithm?

Ex$\mathrm{.}7$ This is from a common coding interview question: Imagine you are given a

list of n integers. Assume they are distinct if that helps you. Give an algorithm

that finds the smallest and the second smallest element in the list, using at most

n $+$ log n comparisons, and explain why your algorithm needs at most n $+$ log n

comparisons. $($Hint: think again of the pairing process we saw in class, when

trying to find the max and the min simultaneously; where is the second smallest

element located? Here, thinking about tennis or chess tournaments may help

you.$)$

$2$For asymptotic notation exercises, if it helps you can think that n is a power of $2.$

$2$