FiltersDone

Question type

Essay

Multiple Choice

Short Answer

True False

Matching

Exam 3: Searching, Sorting, and Complexity Analysis

Show Answer

Share

---

All types

Filters

Study FlashcardsPractice ExamLearn

Question 21

True/False

Review LaterAdd Note

Review Later

In the first step of the quicksort, you begin by selecting the item at the list's midpoint.

A) True
B) False

Correct Answer

verified

Show Answer

Question 22

Multiple Choice

Review LaterAdd Note

Review Later

In the following code, what is the algorithm's complexity? minIndex = 0 CurrentIndex = 1 While currentIndex < len(lyst) : If lyst[currentIndex] < lyst[minIndex]: MinIndex = currentIndex CurrentIndex += 1 Return minIndex

A) O( n ²)
B) O( n )
C) O(log₂ n )
D) O²

E) B) and D)
F) None of the above

Correct Answer

verified

Show Answer

Question 23

True/False

Review LaterAdd Note

The sequential search algorithm does more work to find a target at the beginning of a list than at the end of the list.

What should the missing code be in the following insertion sort algorithm? i = 1 While i < len(myList) : ItemToInsert = myList[i] J = i - 1 While j >= 0: If itemToInsert < myList[j]: MyList[j + 1] = myList[j] J -= 1 Else: Break < missing code > I += 1

In the average case, where many items in a list are out of order, an insertion sort is linear.

In terms of complexity, what is the average case for an insertion sort?

A bubble sort always requires approximately n² comparisons.

Which method of determining the efficiency of algorithms allows you to rate them independently of timings or instruction counts?

Using a binary search, a list of 1 million items requires only 20 comparisons.

This bubble sort has the effect of bubbling the largest items to the end of the list.

Algorithms with linear behavior do more work than those with quadratic behavior.

Which type of algorithm is analogous to how many people organize playing cards in their hands?

In a binary search of an ascending order list, where does the search algorithm begin the search?

How many loops are found in a typical insertion sort?

Which of the following is a method to estimate the efficiency of an algorithm that predicts the amount of work an algorithm performs regardless of the platform?

What should the missing code be in the following algorithm if the goal is to determine how many seconds the algorithm runs? start = time.time() MyCount = 1 For x in range(100) : MyCount *= x Elapsed = time.time() - < missing code >

What is the best case performance of a sequential search?

In terms of complexity, what is the worst-case scenario for an insertion sort?

How can the performance complexity of the following algorithm be described? For x in range(numIterations) : Value = value * x Print(value)

The bubble sort has a complexity of O( n ²).