Question 1 of 10
Algorithm L checks list items one by one from the start until it finds a target or finishes all n items. In the worst case for n = 8, how many item checks does L perform?
- A. 8
- B. 64
- C. 1
- D. 4
Algorithm L checks list items one by one from the start until it finds a target or finishes all n items. In the worst case for n = 8, how many item checks does L perform?
A sorted list has n = 16 values. Binary search roughly halves the remaining region each check. Starting with 16 values, how many halvings until at most one value remains if each step halves exactly (16→8→4→2→1)?
For the same sorted list of n items, as n grows, which statement is true when comparing a full linear scan to binary search?
Algorithm A uses 3n steps for input size n. Algorithm B uses n^2 steps. For n = 5, which is true?
Efficiency in this course is often discussed by counting:
The table compares step counts.
| n | Algorithm P steps | Algorithm Q steps |
|---|---|---|
| 2 | 4 | 8 |
| 4 | 8 | 32 |
| 6 | 12 | ? |
P uses 2n steps. Q uses 2 * n^2 steps. What is Q for n = 6?
Two correct algorithms solve the same problem. Algorithm F takes 50 steps for a certain input. Algorithm G takes 12 steps for that same input. Which statement follows?
Algorithm Exp checks every subset of an n-element set and uses about 2^n checks. Algorithm Lin uses about n checks. For n = 10, which comparison is correct?
A heuristic route finder quickly returns a good path that is not guaranteed to be the shortest. When is a heuristic most appropriate?
For n = 7, a linear scan of all items performs how many item inspections in the worst case?