10.17.2023
Question 1: Consider $f, g, h : Z^{+} \rightarrow R$ with $f(n) = 2n + 1, \; g(n) = n^{2}-1$ and $h(n) = 1 - n$ for all $n$ in $Z^{+}$. Which of the follwing statements is false?
(3 points)
A. $h$ is $O(F)$
B. $f$ is $O(g)$
C. $g$ is $O(h)$
D. $h$ is $O(g)$
Answer
C. $g$ is $O(h)$Question 2: What is the runtime complexity of the following C++ code fragment?
1
2
3
4
sum=0; i=n;
while(i>0){
sum+=i;
i/=2;}
(3 points)
A. $O(n^{2})$
B. $O(\log_{2} n)$
C. $O(1)$
D. $O(n)$
Answer
D. $O(n)$Question 3: Which list of runtime complexities is in the correct order from the slowest (left) to the fastest (right)?
(3 points)
A. $(\log_{2} n), n, n(\log_{2} n), n^{2}, 2^{n}$
B. $(\log_{2} n), n, n^{2}, n(\log_{2} n), 2^{n}$
C. $n, (\log_{2} n), n(\log_{2} n), n^{2}, 2^{n}$
D. $n, (\log_{2} n), n^{2}, n(\log_{2} n), 2^{n}$