Questions: Algorithm Design Basics

Question 1

You need to find a target value in a sorted list of 1,024 elements. At most how many comparisons does binary search require?

• A. 10
• B. 512
• C. 1024
• D. 32

Answer: (A)

Binary search halves the search space with each comparison, so it takes at most log₂(n) comparisons. log₂(1024) = 10. This is the core efficiency advantage over linear search, which would require up to 1,024 comparisons in the worst case.

Question 2

Insertion sort typically runs in O(n log n) time regardless of the input.

• T. True
• F. False

Answer: False

Insertion sort is O(n²) in the worst case (reverse-sorted input), because each new element may need to be compared and swapped all the way back to the start. It is O(n) on nearly-sorted input, which makes it fast in practice for small or nearly-ordered arrays — but it is not O(n log n) in general. Algorithms like merge sort achieve O(n log n) in all cases.

Question 3

Why is writing pseudocode recommended before coding an algorithm?

Model answer: Pseudocode separates the logic of the algorithm from language-specific syntax, making it easier to identify logical errors, edge cases, and termination conditions before implementation details introduce additional complexity.

When you code directly, syntax errors and language quirks distract from logical reasoning. Pseudocode forces you to think through 'what should happen' clearly. Translating correct pseudocode into code is mostly mechanical — the hard thinking is done. Skipping this step embeds logical confusion into implementation, making bugs harder to find.