Question 1

Choose the order of the following growth rates, from slowest to fastest: θ(n³), θ(nlog(n)), θ(n^3/2), θ(2ⁿ). A) θ(n log(n)), θ(n^3/2), θ(n³), θ(2ⁿ) B) θ(n³), θ(n log(n)), θ(n^3/2), θ(2ⁿ) C) θ(n^3/2), θ(n log(n)), θ(n³), θ(2ⁿ) D) θ(2ⁿ), θ(n³), θ(n^3/2), θ(n log(n))

Accepted Answer

The answer of Choose the order of the following growth...

Question 2

How many times can an array with 4,096 elements be cut into two equal pieces?
A) 16
B) 12
C) 10
D) 8

Accepted Answer

The answer of How many times can an array with...

Question 3

In the textbook, we determined that the merge method requires a total of 5n visits. We found that the number of visits required to sort an array of n elements is T(n) = T(n / 2) + T(n / 2) + 5n. What does T(n / 2) describe?
A) the total number of visits to merge sort an array of n elements
B) half the number of visits to merge sort an array of n elements
C) the total number of visits to merge sort an array of n / 2 elements
D) half the number of visits to merge sort an array of n / 2 elements

Accepted Answer

T(n/2) describes the total number of visits required to merge sort an array of n/2 elements, which is the work done for each recursive call. In other words, when we call T(n/2) twice in the equation T(n) = T(n/2) + T(n/2) + 5n, we are doing the merge sort on two subarrays of size n/2 each before merging them together, which takes T(n/2) visits each time. The 5n term represents the work done in merging the two subarrays together.

Question 4

Find the simplest order of growth of the following expression: (n³ + n + 3)². A) θ(n⁵) B) θ(2ⁿ) C) θ(n⁶) D) θ(n⁹)

Accepted Answer

We can simplify the expression as follows: (n³ + n + 3)² = (n2³ + n)² + 3² = θ(n2³) + θ(n) = θ(n⁶) Therefore, the simplest order of growth is θ(n⁶), and the best choice is C.

Question 5

In Big-Oh notation, selection sort is a(n) ____ algorithm. A) O(n²) B) O(1) C) log n D) O(log n²)

Accepted Answer

The answer of In Big-Oh notation, selection sort is a(n)...

Question 6

If the array is already sorted, what is the performance of insertion sort? A) O(n) B) O(n²) C) O(log n) D) O(n log n)

Accepted Answer

If the array is already sorted, then insertion sort simply compares each element with its previous element and moves it forward until it is in the correct position. This means that each element only needs to be compared once, resulting in a time complexity of O(n).

Question 7

Which sort algorithm starts with an initial sequence of size 1, which is assumed to be sorted, and increases the size of the sorted sequence in the array in each iteration?
A) insertion sort
B) selection sort
C) merge sort
D) quicksort

Accepted Answer

Insertion sort starts with a sorted sequence of size 1 and in each iteration, it increases the size of the sorted sequence by one. This is because it takes an element from the unsorted sequence and inserts it into the correct location in the sorted sequence. Therefore, A is the correct choice. Selection sort, merge sort, and quicksort do not follow this approach.

Question 8

How many times can an array with 729 elements be cut into three equal pieces?
A) 4
B) 5
C) 6
D) 7

Accepted Answer

An array with 729 elements can be cut into three equal pieces by dividing it into 3^6 = 729 pieces. Therefore, it can be cut into three equal pieces six times.

Question 9

When the size of an array increases by a factor of 100, the time required by selection sort increases by a factor of ____.
A) 2,000
B) 5,000
C) 10,000
D) 12,000

Accepted Answer

Selection sort has a time complexity of O(n^2), meaning that the time required increases quadratically with the size of the input. If the size of the array increases by a factor of 100, the time required for selection sort will increase by a factor of 100^2 = 10,000. Therefore, the correct answer is C - the time required will increase by a factor of 10,000.

Question 10

Which function has a faster growth rate: θ(n^1/2) or θ(log(n))? A) θ(log(n)) B) θ(n^1/2) C) They are the same. D) They can't be compared.

Accepted Answer

The function θ(n^1/2) has a faster growth rate than θ(log(n)). This is because as n increases, the value of n^1/2 will increase much more rapidly than log(n). As a result, θ(n^1/2) will become much larger much faster than θ(log(n)).

Question 11

Which of the following completes the selection sort method minimumPosition()?
Private static int minimumPosition(int[] a, int from)
{
Int minPos = from;
For (int i = from + 1; i < a.length; i++)
{
________________
}
Return minPos;
}
A) if (a[i] > a[minPos]) { minPos = i; }
B) if (a[i] < a[minPos]) { minPos = i; }
C) if (a[i] < a[j]) { minPos = i; }
D) if (a[i] < a[minPos]) { i = minPos; }

Accepted Answer

The purpose of the minimumPosition() method is to find the index of the minimum value in a given array starting from a specific index (from). The for loop iterates through the array comparing each element to the current minimum (minPos) and updating minPos if it finds a new smaller value. Therefore, the correct choice to complete the method is B, which updates minPos if it finds a value smaller than the current minimum.

Question 12

How many comparisons does selection sort make when sorting an array of length n?
A) n
B) log(2n)
C) n( n + 1) / 2
D) N

Accepted Answer

Selection sort is a comparison-based sorting algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the list. This process repeats until the entire list is sorted.

In selection sort, for each iteration i, the ith smallest element is selected from the remaining unsorted part of the list and placed at its correct position in the sorted part of the list. This requires n-i+1 comparisons.

Therefore, the total number of comparisons in selection sort can be calculated as:

n-1 + n-2 + ... + 2 + 1 
= n(n-1)/2 
= n^2/2 - n/2 
= O(n^2)

So, the answer is C: n(n+1)/2. This is the formula for the sum of the first n natural numbers, which is equivalent to the total number of comparisons in selection sort.

Question 13

If you increase the size of a dataset fivefold, how much longer does it take to sort it with the selection sort algorithm?
A) Approximately 5 times longer
B) Approximately 20 times longer
C) Approximately 25 times longer
D) Approximately 100 times longer

Accepted Answer

The answer of If you increase the size of a...

Question 14

Consider the following code snippet:
Public static void sort(int[] a) {
For (int i = 1; i < a.length; i++)
{
int next = a[i];
int j = i;
while (j > 0 && a[j - 1] > next)
{
a[j] = a[j - 1];
j--;
}
a[j] = next;
}
}
What sort algorithm is used in this code?
A) insertion sort
B) selection sort
C) merge sort
D) quicksort

Accepted Answer

The code uses the insertion sort algorithm, which sorts an array by gradually building up a sorted subarray at the beginning of the array. It takes the next element from the unsorted part of the array and inserts it in its proper position in the sorted subarray. This process is repeated until all elements are sorted.

Question 15

In general, the expression ____ means that f grows no faster than g. A) f(n) = log g B) f(n) = log g² C) f(n) = O(g(n)) D) g(n) = O(f(n))

Accepted Answer

The big O notation means that the function grows no faster than the stated function. Therefore, f(n) = O(g(n)) means that f grows no faster than g.

Question 16

What is the worst-case performance of insertion sort? A) O(n) B) O(n²) C) O(log (n)) D) O(n log (n))

Accepted Answer

The answer of What is the worst-case performance of insertion...

Question 17

Which sort algorithm starts by cutting the array in half and then recursively sorts each half?
A) insertion sort
B) selection sort
C) merge sort
D) quicksort

Accepted Answer

The sort algorithm that starts by cutting the array in half and then recursively sorts each half is merge sort. It is efficient and has a time complexity of O(n log n), making it a good choice for large data sets. Insertion sort and selection sort have time complexities of O(n^2) and are not efficient for large data sets. Quicksort has a time complexity of O(n^2) in the worst case, although it can be efficient in some cases. However, merge sort is a more reliable choice for general-purpose sorting.

Question 18

Find the simplest order of growth of the following expression: n³ + log(n⁵). A) θ(n³) B) θ(n³+ log(n)) C) θ(log(n⁵)) D) θ(n+ log(n))

Accepted Answer

The answer of Find the simplest order of growth of...

Question 19

If f(n) = O(g(n)) and g(n) = O(f(n)), what else must be true?
I f(n) = Ω(g(n))
II g(n) = Ω(f(n))
III f(n) = θ(g(n))
A) I
B) II
C) I and II
D) I, II, and III

Accepted Answer

The answer of If f(n) = O(g(n)) and g(n) =...

Question 20

Which notation, big-Oh, theta, or omega describes the growth rate of a function?
I big-Oh
II theta
III omega
A) I
B) II and III
C) I and II
D) I, II, and III

Accepted Answer

The answer of Which notation, big-Oh, theta, or omega describes...

Quiz 14: Sorting and Searching

Choose the order of the following growth rates, from slowest to fastest: θ(n³) , θ(nlog(n) ) , θ(n^3/2) , θ(2ⁿ) .

How many times can an array with 4,096 elements be cut into two equal pieces?

In the textbook, we determined that the merge method requires a total of 5n visits. We found that the number of visits required to sort an array of n elements is T(n) = T(n / 2) + T(n / 2) + 5n. What does T(n / 2) describe?

Find the simplest order of growth of the following expression: (n³ + n + 3) ².

In Big-Oh notation, selection sort is a(n) ____ algorithm.

If the array is already sorted, what is the performance of insertion sort?

Which sort algorithm starts with an initial sequence of size 1, which is assumed to be sorted, and increases the size of the sorted sequence in the array in each iteration?

How many times can an array with 729 elements be cut into three equal pieces?

When the size of an array increases by a factor of 100, the time required by selection sort increases by a factor of ____.

Which function has a faster growth rate: θ(n^1/2) or θ(log(n) ) ?

Which of the following completes the selection sort method minimumPosition() ? Private static int minimumPosition(int[] a, int from) { Int minPos = from; For (int i = from + 1; i < a.length; i++) { ________________ } Return minPos; }

How many comparisons does selection sort make when sorting an array of length n?

If you increase the size of a dataset fivefold, how much longer does it take to sort it with the selection sort algorithm?

Consider the following code snippet: Public static void sort(int[] a) { For (int i = 1; i < a.length; i++) { int next = a[i]; int j = i; while (j > 0 && a[j - 1] > next) { a[j] = a[j - 1]; j--; } a[j] = next; } } What sort algorithm is used in this code?

In general, the expression ____ means that f grows no faster than g.

What is the worst-case performance of insertion sort?

Which sort algorithm starts by cutting the array in half and then recursively sorts each half?

Find the simplest order of growth of the following expression: n³ + log(n⁵) .

If f(n) = O(g(n) ) and g(n) = O(f(n) ) , what else must be true? I f(n) = Ω(g(n) ) II g(n) = Ω(f(n) ) III f(n) = θ(g(n) )

Which notation, big-Oh, theta, or omega describes the growth rate of a function? I big-Oh II theta III omega