On a CPU that executes $109$ operations per second, algorithm A took $0\mathrm{.}1$ seconds to run on an input

of size $106$

and $10$ seconds to run on an input of size $107$ On a CPU that executes ${10}^9$ operations per second, algorithm A took $0\mathrm{.}1$ seconds to run on an input

of size ${10}^6$ and $10$ seconds to run on an input of size ${10}^7.$ What is the asymptotic running time of

algorithm $A?$

You are tasked with solving a problem on a list with $1000$ elements. There are three algorithms $1,2,$

and $3$ available, with the following running times: $T_1=100n,T_2=10nlo{g}_{10}n,$ and $T_3=\frac{n^2}{10}.$

Which algorithm will be the fastest on your input?

A$.$ Algorithm $2$

B$.$ Algorithms $1$ and $2$

C$.$ Algorithms $1$ and $3$

D$.$ Algorithm $1$

E$.$ Algorithm $3$

What is the asymptotic running time of the following algorithm in terms of elementary operations?

Count only operations on line $5.$

A$.(n)$

B$.(log(logn))$

C$.((logn{)}^2)$

D$.(n^2)$

E$.(nlogn)$ What is the number of comparisons of the following algorithm in the AVERAGE case? Count only

comparisons involving an element of $a($those in line $3).$ You may assume that each element of $a$ is

either $0$ or $1,$ chosen uniformly $($that is$,$ with probability $\frac{1}{2}).$

A$.\frac{n}{2}$

B$.2(1-2^{-n})$

C$.\frac{n}{2n^2-1}$

D$.n$

E$.2nlogn$

What is the asymptotic relation between functions $sin(n)$ and $cos(n)?$ Assume that $n$ represents an

angle in degrees.

A$.$ There is no asymptotic relation

B$.sin(n)$ is $O(1)$ and $cos(n)$ is $(1)$

C$.sin(n)$ is $(cos(n))$

D$.sin(n)$ is $(cos(n))$

E$.sin(n)$ is $O(cos(n))$

Consider three functions $f,g,$ and $h$ such that $f=O(g),g=O(f),$ and $h(n)=n*f(n).$ Which of

the following statements is the most accurate?

A$.h$ is not asymptotically related to $g$

B$.h$ is $(g)$ and not $O(g)$

C$.h$ is $(g)$

D$.h$ is $O(g)$ and not $(g)$

E$.h$ is $O(g)$ What is the most accurate expression for the running time of the following algorithm in terms of

elementary operations? Count assignments, comparisons, and arithmetic operations. a and $b$ are lists

of integers.

You evaluate a sorting algorithm by measuring its running time on a few inputs of increasing sizes

and the results show that, on these particular inputs, the runtime was $(nlogn).$ Which algorithm is

NOT consistent with your observations?

A$.$ Mergesort

B$.$ Insertion sort

C$.$ None $($they are all consistent$)$

D$.$ Selection sort

E$.$ Quicksort

You evaluate a sorting algorithm by measuring its running time on a few inputs of increasing sizes and

the results show that, on these particular inputs, the runtime was $(n).$ Which algorithm is consistent

with your observations? You evaluate a sorting algorithm by measuring its running time on a few inputs of increasing sizes

and the results show that, on these particular inputs, the runtime was $(n^2).$ Which algorithm is NOT

consistent with your observations?

A$.$ Selection sort

B$.$ None $($they are all consistent$)$

C$.$ Insertion sort

D$.$ Quicksort

E$.$ Mergesort