Lesson test: How cost grows

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

How cost grows

1.[2p]
What exactly does $f (n) = O (g (n))$ assert?

There exist $c > 0$ and $n_{0}$ with $f (n) \leq c g (n)$ for every $n \geq n_{0}$

Correct

$f (n) \leq g (n)$ for every $n$

The answer is: There exist $c > 0$ and $n_0$ with $f(n) \le c\,g(n)$ for every $n \ge n_0$

$f$ and $g$ grow at the same rate

The answer is: There exist $c > 0$ and $n_0$ with $f(n) \le c\,g(n)$ for every $n \ge n_0$

$f (n) / g (n)$ tends to 1 as $n$ grows

The answer is: There exist $c > 0$ and $n_0$ with $f(n) \le c\,g(n)$ for every $n \ge n_0$

2.[2p]
Using the bound $5 n \leq 0.5 n^{2}$ and $100 \leq n^{2}$ , the proof that $3 n^{2} + 5 n + 100 = O (n^{2})$ gives a witness constant $c$ . What is $c$ ?

CorrectNot quite: 4.5

3.[2p]
The statement "quicksort is at least $O (n \log n)$ " is a well-formed claim.

True

The answer is: False

False

Correct

4.[3p]
Which of these are true of $f (n) = 6 n^{2} + 40 n$ ?

Select all that apply

$f (n) = O (n^{2})$

Correct

$f (n) = Θ (n^{2})$

Correct

$f (n) = O (n^{3})$

Correct

$f (n) = Θ (n)$

The answer is: $f(n) = O(n^2)$, $f(n) = \Theta(n^2)$, $f(n) = O(n^3)$

5.[2p]
A cubic algorithm takes 1.0 second on $n = 1000$ . How many seconds does it take on $n = 5000$ ?

CorrectNot quite: 125

6.[2p]
A loop runs $n$ times, and its body halves a counter starting at $n$ until the counter reaches 1. The total cost is

$Θ (n \log n)$

Correct

$Θ (n^{2})$

The answer is: $\Theta(n \log n)$

$Θ (n)$

The answer is: $\Theta(n \log n)$

$Θ (\log n)$

The answer is: $\Theta(n \log n)$

7.[2p]
Why does $O (\log n)$ need no logarithm base?

Changing base multiplies by a constant, and constants are discarded

Correct

Base 2 is assumed by convention and the others are wrong

The answer is: Changing base multiplies by a constant, and constants are discarded

Logarithms of different bases have different growth rates

The answer is: Changing base multiplies by a constant, and constants are discarded

The base cancels against the input size

The answer is: Changing base multiplies by a constant, and constants are discarded

8.[3p]
Put these costs in order from slowest-growing to fastest-growing.

$n \log_{2} n$
$n$
$2^{n}$
$n^{2}$
$\log_{2} n$

Show the answer

b, e, d, a, c

9.[2p]
A "galactic algorithm" such as the current record for matrix multiplication is one that

has a better exponent but constants so large it never wins at any feasible input size

Correct

has been proved incorrect

The answer is: has a better exponent but constants so large it never wins at any feasible input size

runs only on distributed machines

The answer is: has a better exponent but constants so large it never wins at any feasible input size

has a worse asymptotic cost but better real performance

The answer is: has a better exponent but constants so large it never wins at any feasible input size

1.[2p] What exactly does f(n)=O(g(n)) assert?

2.[2p] Using the bound 5n≤0.5n2 and 100≤n2, the proof that 3n2+5n+100=O(n2) gives a witness constant c. What is c?

3.[2p] The statement "quicksort is at least O(nlogn)" is a well-formed claim.

4.[3p] Which of these are true of f(n)=6n2+40n?

5.[2p] A cubic algorithm takes 1.0 second on n=1000. How many seconds does it take on n=5000?

6.[2p] A loop runs n times, and its body halves a counter starting at n until the counter reaches 1. The total cost is

7.[2p] Why does O(logn) need no logarithm base?

8.[3p] Put these costs in order from slowest-growing to fastest-growing.

9.[2p] A "galactic algorithm" such as the current record for matrix multiplication is one that

1.[2p]
What exactly does $f (n) = O (g (n))$ assert?

2.[2p]
Using the bound $5 n \leq 0.5 n^{2}$ and $100 \leq n^{2}$ , the proof that $3 n^{2} + 5 n + 100 = O (n^{2})$ gives a witness constant $c$ . What is $c$ ?

3.[2p]
The statement "quicksort is at least $O (n \log n)$ " is a well-formed claim.

4.[3p]
Which of these are true of $f (n) = 6 n^{2} + 40 n$ ?

5.[2p]
A cubic algorithm takes 1.0 second on $n = 1000$ . How many seconds does it take on $n = 5000$ ?

6.[2p]
A loop runs $n$ times, and its body halves a counter starting at $n$ until the counter reaches 1. The total cost is

7.[2p]
Why does $O (\log n)$ need no logarithm base?

8.[3p]
Put these costs in order from slowest-growing to fastest-growing.

9.[2p]
A "galactic algorithm" such as the current record for matrix multiplication is one that