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 1

True/False

Review LaterAdd Note

Review Later

The amount of work of a logarithmic algorithm is proportional to the log₂ of the problem size.

A) True
B) False

Correct Answer

verified

Show Answer

Question 2

Multiple Choice

Review LaterAdd Note

Review Later

What is the complexity of a selection sort?

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

E) A) and D)
F) B) and D)

Correct Answer

verified

Show Answer

Question 3

True/False

Review LaterAdd Note

The number of Python instructions executed in an algorithm will differ from the number of machine language instructions executed.

On sorted data, you can use a binary search.

In a bubble sort, each pass through the main loop selects a single item to be moved.

Which of the following is a common way to measure the time cost of an algorithm?

All algorithms that perform the same task take the same amount of time to complete.

How can the following algorithm be described? Position = 0 While position < len(lyst) : If target == lyst[ position ]: Return position Position += 1 Return -1

The in operator performs a binary search algorithm.

The result of fib(4) is 8.

Why is the efficiency of algorithms desirable?

How can an algorithm be described in which the work it does grows as a function of the square of the problem size?

What is the worst-case complexity of a binary search?

What term best describes the following code? X = myList[ i ] MyList[ i ] = myList[ j ] MyList[ j ] = x

In a selection sort, the outer loop executes n - 1 times.

An algorithm that uses the exact same Python code run on two different machines should have the same performance data.

Python's in operator is implemented as a method named __contains__ in the list class.

The merge sort employs a recursive, divide-and-conquer strategy to break the O( n² ) barrier.

What does the Python time() function return?

The first two numbers in the Fibonacci sequence are 1s, and each number after that is the sum of the previous two numbers.