Questions: Algorithm Analysis and Complexity Classes

Question 1

What does 'NP' stand for in the complexity class NP?

• A. Not Polynomial
• B. Non-deterministic Polynomial
• C. Nearly Polynomial
• D. Nondeterministic Provable

Answer: (B)

NP stands for Nondeterministic Polynomial time. It refers to problems that a nondeterministic Turing machine could solve in polynomial time — equivalently, problems whose proposed solutions can be *verified* in polynomial time by a deterministic machine. 'Not Polynomial' is the most common misconception; NP actually includes problems that may or may not be solvable in polynomial time (that's the open P vs NP question).

Question 2

For large input sizes, an O(n²) algorithm is generally slower than an O(n log n) algorithm.

• T. True
• F. False

Answer: False

Big-O describes asymptotic behavior — how runtime grows as n approaches infinity. For small n, constants and lower-order terms dominate, so an O(n²) algorithm with a tiny constant can outperform an O(n log n) algorithm with a large one. The statement is eventually true for sufficiently large n, but 'always' is wrong. In practice, the crossover point matters, which is why algorithm selection depends on expected input size.

Question 3

Explain in your own words why binary search runs in O(log n) time.

Model answer: Binary search halves the search space at each step. Starting with n elements, after one comparison you have n/2 remaining; after two, n/4; and so on. The number of steps needed to reduce n to 1 is log₂(n), because you are asking 'how many times can I halve n before reaching 1?' — which is the definition of the base-2 logarithm.

The halving argument is the key intuition. Any algorithm that discards a constant fraction of its remaining work at each step will have logarithmic complexity. This is why binary search, balanced BST operations, and many divide-and-conquer algorithms share the O(log n) signature — they all reduce the problem size multiplicatively rather than additively.