Question $1(2$ points$)$

For comparison$-$based sorting algorithms, a lower$-$bound of $($nlogn$)$ on the worstcase running time. To prove that we modeled the execution of any sorting lgorithm with a binary tree. Following the same reasoning, give an upper boun the number of inputs of size $n$ for which the algorithm can take logarithmic

e$.$ Choose only one answer.

$2^{O(n)}$

$O(logn)$

$O(\sqrt[\phantom{2}]{n})$

$O(n)$

$O(1)$