Question 1 of 10
In the worst case, how many elements does a linear scan inspect in a list of n = 9 items?
- A. 81
- B. 3
- C. 9
- D. 18
In the worst case, how many elements does a linear scan inspect in a list of n = 9 items?
A sorted list of 32 items is searched by binary search that halves each time: 32→16→8→4→2→1. How many halvings is that?
Algorithm U takes 4n steps. Algorithm V takes 20 steps regardless of n. For n = 3, which uses fewer steps?
For large n on a sorted list, why is binary search generally fewer steps than scanning every item?
An instance of a problem includes:
Step-count table:
| n | Algo X | Algo Y |
|---|---|---|
| 1 | 2 | 2 |
| 2 | 4 | 4 |
| 3 | 6 | 8 |
| 4 | 8 | 16 |
X matches 2n. Y matches 2^n. For n = 5, which predicted pair is correct?
Some problems have no known efficient exact algorithm for large inputs. A common response is to:
Algorithm Nested runs an outer loop n times and an inner loop n times, doing 1 step in the inner body (about n^2 steps). For n = 6, about how many inner-body steps?
Which pair correctly contrasts decision and optimization problems?
For n = 4, algorithm Linear does 4 steps and algorithm Square does 16 steps. Which uses more steps?