DSABook – Review questions

5.5 Review questions

This final section contains some review questions about the contents of this chapter.

5.5.1 Review questions: Upper bounds

Answer TRUE or FALSE.

The Sequential Search algorithm is in $O(n^2)$ .

True
False

Recall that $O(n^2)$ means that the program has no inputs that cost more than this.
A proposed upper bound can be much higher than the actual cost of the program, and still be correct.

For sequential search, the best case occurs when:

The search target is near the front of the array
The array is small
The algorithm is implemented efficiently
The search key is small

It is a serious misunderstanding of algorithm analysis to think that best case is related to input size. The array being small has nothing to do with what is the best case input (of a given size).
Implementation of an algorithm (as a program) has nothing to do with the algorithm’s best case.
Since sequential search can be used on an unsorted array, the value for the search key (large or small) might have nothing to do with where the record with that key will be in the array.

What is the smallest integer $k$ such that $\sqrt n$ is in $O(n^k)$ ?

$\sqrt n = n^{0.5}$
What is the smallest integer greater than 0.5?

What is the smallest integer $k$ such that $n \log n$ is in $O(n^k)$ ?

$n \log n$ is bigger than $n^{1}$ .
So, that means 1 is too small.
But, $n \log n$ is less than $n^2$ .
Actually $n \log n$ is less than $n^{1+a}$ even for tiny positive values of $a$ .

Which of these is the best upper bound for a growth rate of $5n + 3$ ?

The simplifying rules tell us that we can drop constants and lower order terms from a polynomial that defines the growth rate.

Which of these is the best upper bound for a growth rate of $5n + 3$ ?

$O(n \log n)$
$O(n^2)$
$O(\log n)$
$O(1)$

The simplifying rules tell us that we can drop constants and lower order terms from a polynomial that defines the growth rate.
If you don’t see a tight upper bound, pick the smallest bound that is larger.

5.5.2 Review questions: Asymptotic notations

Answer TRUE or FALSE.

Big-Theta notation ( $\Theta$ ) defines an equivalence relation on the set of functions.

True
False

An equivalence relation is a relation that is reflexive, symmetric, and transitive.
Big-Theta notation is like $=$ .
$=$ is an equivalence relation.

Answer TRUE or FALSE.

The Sequential Search algorithm is $\Theta(n^2)$ .

True
False

Recall that $\Theta(n^2)$ means that all program inputs (beyond a certain, small size) run within a constant factor of $n^2$ .
Theta means that the program is not growing too much slower, nor too much faster, than the claimed growth rate.
Sequential search grows much slower than $n^2$ .

Determine the proper relationship between the following pair of functions.

$\begin{align*} f(n) &= \log n^2 \\ g(n) &= \log n + 5 \end{align*}$

$f(n)$ is $\Theta(g(n))$
$f(n)$ is in $\Omega(g(n))$
$f(n)$ is in $O(g(n))$

if $\lim \frac{f(n)}{g(n)} \rightarrow 0$ , then $f(n)$ is in $O(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow$ constant, then $f(n)$ is $\Theta(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow \infty$ , then $f(n)$ is in $\Omega(g(n))$ .

Determine the proper relationship between the following pair of functions.

$\begin{align*} f(n) &= \sqrt n \\ g(n) &= \log n^2 \end{align*}$

$f(n)$ is $\Omega(g(n))$
$f(n)$ is $\Theta(g(n))$
$f(n)$ is in $O(g(n))$

if $\lim \frac{f(n)}{g(n)} \rightarrow 0$ , then $f(n)$ is in $O(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow$ constant, then $f(n)$ is $\Theta(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow \infty$ , then $f(n)$ is in $\Omega(g(n))$ .

Determine the proper relationship between the following pair of functions.

$\begin{align*} f(n) &= \log^2 n \\ g(n) &= \log n \end{align*}$

$f(n)$ is $\Omega(g(n))$
$f(n)$ is $\Theta(g(n))$
$f(n)$ is in $O(g(n))$

if $\lim \frac{f(n)}{g(n)} \rightarrow 0$ , then $f(n)$ is in $O(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow$ constant, then $f(n)$ is $\Theta(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow \infty$ , then $f(n)$ is in $\Omega(g(n))$ .

Determine the proper relationship between the following pair of functions.

$\begin{align*} f(n) &= n \\ g(n) &= \log^2 n \end{align*}$

$f(n)$ is $\Omega(g(n))$
$f(n)$ is $\Theta(g(n))$
$f(n)$ is in $O(g(n))$

if $\lim \frac{f(n)}{g(n)} \rightarrow 0$ , then $f(n)$ is in $O(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow$ constant, then $f(n)$ is $\Theta(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow \infty$ , then $f(n)$ is in $\Omega(g(n))$ .

Determine the proper relationship between the following pair of functions.

$\begin{align*} f(n) &= n \log n + n \\ g(n) &= \log n \end{align*}$

$f(n)$ is $\Omega(g(n))$
$f(n)$ is $\Theta(g(n))$
$f(n)$ is in $O(g(n))$

if $\lim \frac{f(n)}{g(n)} \rightarrow 0$ , then $f(n)$ is in $O(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow$ constant, then $f(n)$ is $\Theta(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow \infty$ , then $f(n)$ is in $\Omega(g(n))$ .

Determine the proper relationship between the following pair of functions.

$\begin{align*} f(n) &= \log n^2 \\ g(n) &= (\log n)^2 \end{align*}$

$f(n)$ is $\Omega(g(n))$
$f(n)$ is $\Theta(g(n))$
$f(n)$ is in $O(g(n))$

if $\lim \frac{f(n)}{g(n)} \rightarrow 0$ , then $f(n)$ is in $O(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow$ constant, then $f(n)$ is $\Theta(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow \infty$ , then $f(n)$ is in $\Omega(g(n))$ .

Determine the proper relationship between the following pair of functions.

$\begin{align*} f(n) &= 10 \\ g(n) &= \log 10 \end{align*}$

$f(n)$ is $\Omega(g(n))$
$f(n)$ is $\Theta(g(n))$
$f(n)$ is in $O(g(n))$

if $\lim \frac{f(n)}{g(n)} \rightarrow 0$ , then $f(n)$ is in $O(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow$ constant, then $f(n)$ is $\Theta(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow \infty$ , then $f(n)$ is in $\Omega(g(n))$ .

Determine the proper relationship between the following pair of functions.

$\begin{align*} f(n) &= 2^n \\ g(n) &= 10 n^2 \end{align*}$

$f(n)$ is $\Omega(g(n))$
$f(n)$ is $\Theta(g(n))$
$f(n)$ is in $O(g(n))$

if $\lim \frac{f(n)}{g(n)} \rightarrow 0$ , then $f(n)$ is in $O(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow$ constant, then $f(n)$ is $\Theta(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow \infty$ , then $f(n)$ is in $\Omega(g(n))$ .

Determine the proper relationship between the following pair of functions.

$\begin{align*} f(n) &= 2^n \\ g(n) &= n \log n \end{align*}$

$f(n)$ is $\Omega(g(n))$
$f(n)$ is $\Theta(g(n))$
$f(n)$ is in $O(g(n))$

if $\lim \frac{f(n)}{g(n)} \rightarrow 0$ , then $f(n)$ is in $O(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow$ constant, then $f(n)$ is $\Theta(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow \infty$ , then $f(n)$ is in $\Omega(g(n))$ .

Determine the proper relationship between the following pair of functions.

$\begin{align*} f(n) &= 2^n \\ g(n) &= 3^n \end{align*}$

$f(n)$ is $\Omega(g(n))$
$f(n)$ is $\Theta(g(n))$
$f(n)$ is in $O(g(n))$

if $\lim \frac{f(n)}{g(n)} \rightarrow 0$ , then $f(n)$ is in $O(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow$ constant, then $f(n)$ is $\Theta(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow \infty$ , then $f(n)$ is in $\Omega(g(n))$ .

Determine the proper relationship between the following pair of functions.

$\begin{align*} f(n) &= 2^n \\ g(n) &= n^n \end{align*}$

$f(n)$ is $\Omega(g(n))$
$f(n)$ is $\Theta(g(n))$
$f(n)$ is in $O(g(n))$

if $\lim \frac{f(n)}{g(n)} \rightarrow 0$ , then $f(n)$ is in $O(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow$ constant, then $f(n)$ is $\Theta(g(n))$ .
if $\lim \frac{f(n)}{g(n)} \rightarrow \infty$ , then $f(n)$ is in $\Omega(g(n))$ .

Which of these is the best lower bound for a growth rate of $5n + 3$ ?

The simplifying rules tell us that we can drop constants and lower order terms from a polynomial that defines the growth rate.

For what value of $k$ is $\sqrt n = \Theta(n^k)$ ? (Answer in decimals, not fractions)

$\sqrt n = n^{0.5}$

If we know that algorithm X is $\Theta(n)$ in the average case, then what can we say about its TIGHTEST upper bound?

It is $O(n)$ in the average case.
It is $O(n)$ or greater in the average case, but we don’t have enough information to say more.
It is $O(n)$ or less in the average case, but we don’t have enough information to say more.
We don’t have enough information to say.

What is the definition of $\Theta(n)$ ?
Being $\Theta(n)$ means that we know a tight bound (both the upper and the lower bounds match).
If X is $\Theta(n)$ , then it is both $O(n)$ and $\Omega(n)$ .

5.5.3 Review questions: Analysing problems

Answer TRUE or FALSE.

No algorithm for searching in an unsorted array can be worse than $O(n)$ since any algorithm must look at every value in the array in the worst case.

True
False

Do you think that sequential search is the only algorithm to search an unsorted array?
Can’t someone write a worse algorithm, perhaps by adding unnecessary work?

Answer TRUE or FALSE.

The upper bound for a problem is defined as the upper bound cost for the worst algorithm that we know.

True
False

There is no limit to how bad someone might make an algorithm. So this can’t make sense as a definition.

Answer TRUE or FALSE.

The upper bound for a problem is defined as the upper bound cost for the best algorithm that we know.

True
False

This comes straight from the definition for the upper bound of a problem.

Answer TRUE or FALSE.

The lower bound for a problem is defined as the cost of the best algorithm that we know.

True
False

Just because we know some algorithm does not mean that there does not exist some better algorithm.
The lower bound for a problem is the best that an algorithm COULD be, not just what we happen to know.

Answer TRUE or FALSE.

The lower bound for a problem is defined as the least cost that any algorithm could reach.

True
False

This comes straight from the definition for the lower bound of a problem.

Answer TRUE or FALSE.

The worst case upper bound for sorting an array is $O(n \log n)$ since this is the cost of the best algorithm (in the worst case) that we know about.

True
False

This comes straight from the definition for problem upper bound.

Answer TRUE or FALSE.

The lower bound of the sorting problem is $\Omega(n \log n)$ because we can prove that this is the best cost that any sorting algorithm could reach.

True
False

This comes straight from the definition of a problem lower bound.

The upper bound for a problem is defined to be:

The cost of the best algorithm that we know for the problem
The cost of the worst algorithm that we know for the problem
The same as the lower bound for the problem
The cost of the worst case input for the problem

For a given problem, it is possible to write an algorithm that is as bad as we want. So defining a bound in terms of bad algorithms is not useful.
We look at the worst-case input to determine the worst-case upper bound for an algorithm, not a problem.
To get the upper bound for a problems, we compare the cost for each algorithm that we know.
The upper bound of the problem is the upper bound of the best known algorithm.

The lower bound for a problem is defined to be:

The best possible cost for any algorithm that solves the problem
The cost of the best algorithm that we know for the problem
The same as the upper bound for the problem
The cost of the best case input for the problem
The maximum cost that any algorithm to solve the problem could have

Upper and lower bounds are used to describe to what we know, and we do not always know that these are the same for a given algorithm.
Lower bound refers to the class of inputs that we are considering (best, average, or worst-case). So it does NOT necessarily have anything to do with the best-case input.
The cost of the best algorithm that we know sets a limit on the upper bound of the problem, not the lower bound.
The lower bound refers to the best possible cost (for the class of inputs, such as worst-case) for ANY algorithm that solves the problem.

If the upper and lower bounds for a problem meet then:

We can say that we understand the runtime cost of the problem
We are ready to implement the solution to the problem
The universe explodes
The problem is $\Theta(n)$

The universe hasn’t exploded yet.
Just because the bounds meet, it does not mean that the cost is $\Theta(n)$ .
We might need to implement an algorithm even if we are not certain that it is the best.
When the bounds meet, then we know for certain if an algorithm to solve that problem is best (within a constant factor).

Which of the following is NOT relevant to the sorting problem lower bounds proof?

The worst-case cost for Bubble sort is $\Theta(n^2)$
The number of permutations for $n$ records is $n!$
A tree with $n$ nodes has a depth of at least $\log n$
Any sorting algorithm can be modeled using a decision tree

The proof uses decision trees to model sorting algorithms.
The number of permutations affects the size of the decision tree.
Given a tree of a certain size, we can compute its minimum depth.
The cost of Bubble Sort does not affect the cost of other sorts.

$\log n!$ is:

Since $n! \leq n^n$ , it follows that $\log n! \leq \log n^n = n \log n$ . So that eliminates anything bigger than $n \log n$ .
There are $n$ terms in $n!$ , and you need to take the log of each of them. Since they have some size, it has to be much more than $\log n$ .
It turns out to be worse than just $n$ .

A decision tree is:

A model for the behaviour of an algorithm based on the decisions that it makes
A tree that helps you to decide which permutation sorts the input
A tree that searches for the lower bound for sorting
A search tree

A decision tree is not a search tree.
A decision tree is a model for behaviour, not an algorithm.

5.5.4 Review questions: Common misunderstandings

Answer TRUE or FALSE.

For all algorithms, if we completely understand the running time analysis, then the upper bound and lower bound will be the same.

True
False

Upper and lower bounds are only different when we do not completely understand the cost for the algorithm.

Answer TRUE or FALSE.

The worst case for sequential search occurs when the last element of the array is the value being searched for.

True
False

Worst case cost refers to the most expensive problem instance AS THE INPUT GETS BIG.
Since, for any given array (regardless of size), the most expensive problem instance occurs when the search value is in the last position of the array, this is indeed the worst case.

Answer TRUE or FALSE.

The best case for the sequential search algorithm occurs when the array has only a single element.

True
False

Best case cost refers to a best problem instance AS THE INPUT GETS BIG.
So it makes no sense to talk about a growth rate or a best case of a fixed input size.
The best case for sequential search occurs when the first element of the array (for whatever size) is the value being searched for.

Answer TRUE or FALSE.

The worst case for the sequential search algorithm occurs when the array size tends to infinity.

True
False

Worst case cost refers to the most expensive problem instance AS THE INPUT GETS BIG.
That is, worst case does not refer to what the input size it.
It refers to which input of a particular size is the worst one.
The worst case for sequential search occurs when the last element of the array (for whatever size) is the value being searched for.