HomeSubjectsUniversityBlogAbout

Complexity & Optimization

Topic in Data Structures & Algorithms

210 total MCQsShowing 30 with explanations10 Easy10 Medium10 Hard
Start Timed Quiz on Complexity & OptimizationBack to Data Structures & Algorithms

About This Topic

Computational complexity measures how an algorithm's time and memory grow with input size, and classifies problems by the resources needed to solve them. Complexity-theory MCQs define P as problems solvable in polynomial time, NP as problems whose solutions can be verified in polynomial time, and NP-complete and NP-hard problems through polynomial-time reductions, for example from Clique to Vertex Cover. PSPACE and its relationship to NP may also be asked. On the optimisation side, questions cover space-time trade-offs, memoisation, tail-call optimisation, loop unrolling, cache-friendly data locality, amortised analysis, and applying the master theorem to divide-and-conquer recurrences.

Below are 30 practice questions from a pool of 210 Complexity & Optimization MCQs, one of 12 topics in Data Structures & Algorithms. Each shows the correct answer with an explanation; when you are ready, take a timed quiz to test recall under exam conditions.

Practice Questions

Each question below shows the correct answer with a full explanation. Use these to build conceptual understanding before attempting a timed quiz.

Complexity & OptimizationEasy

Q1. Which is more efficient: O(n) or O(n log n)?

  1. A.Depends on constants
  2. B.O(n) is more efficient✓ Correct
  3. C.O(n log n) is better
  4. D.They are equivalent

Explanation

O(n) is more efficient than O(n log n) because n grows slower than n log n for large values of n.

Report an error in this question

Complexity & OptimizationEasy

Q2. Which is faster: O(log n) or O(√n)?

  1. A.They are equivalent
  2. B.O(log n) is faster✓ Correct
  3. C.O(√n) is faster
  4. D.Cannot compare them

Explanation

O(log n) grows slower than O(√n) for large n. For example, when n = 1,000,000: log n ≈ 20 while √n = 1,000.

Report an error in this question

Complexity & OptimizationMedium

Q3. What is an NP-complete problem?

  1. A.A problem that cannot be solved at all
  2. B.A problem with no known algorithm existing
  3. C.A problem in NP as hard as any NP problem✓ Correct
  4. D.A problem that runs in constant time always

Explanation

An NP-complete problem is in NP and is as hard as any NP problem: every problem in NP can be reduced to it in polynomial time.

Report an error in this question

Complexity & OptimizationEasy

Q4. What is the time complexity of finding the maximum element in an unsorted array?

  1. A.O(n)✓ Correct
  2. B.O(n^2)
  3. C.O(1)
  4. D.O(log n)

Explanation

Finding the maximum in an unsorted array requires examining every element, taking O(n) time.

Report an error in this question

Complexity & OptimizationMedium

Q5. What is the relationship between P and NP?

  1. A.P and NP are completely disjoint sets
  2. B.P = NP has been proven true conclusively
  3. C.NP ⊆ P has been proven true conclusively
  4. D.P ⊆ NP, but whether P = NP is open✓ Correct

Explanation

Every problem in P is also in NP (P ⊆ NP). Whether P = NP (every NP problem has a polynomial solution) is one of the most important open problems in computer science.

Report an error in this question

Complexity & OptimizationMedium

Q6. What is an NP-hard problem?

  1. A.A problem with a known polynomial time solution
  2. B.A problem that is always in the class P
  3. C.A problem that is easy to solve efficiently
  4. D.A problem at least as hard as NP-complete problems✓ Correct

Explanation

An NP-hard problem is at least as hard as NP-complete problems. It may or may not be in NP (its solution may not be verifiable in polynomial time).

Report an error in this question

Complexity & OptimizationEasy

Q7. What is the significance of O(n!) complexity?

  1. A.It is essentially the same as O(n^2) complexity class
  2. B.It is classified as a polynomial time complexity class
  3. C.It is very efficient for all possible input sizes given
  4. D.It is extremely inefficient, growing super-exponentially✓ Correct

Explanation

O(n!) (factorial) is one of the fastest-growing complexities, making algorithms with this complexity practical only for very small inputs.

Report an error in this question

Complexity & OptimizationEasy

Q8. What does NP stand for in computational complexity?

  1. A.New computational Problems class
  2. B.Non-deterministic Polynomial time✓ Correct
  3. C.Not Polynomial time class
  4. D.No Proof available for it

Explanation

NP stands for Non-deterministic Polynomial time: problems whose solutions can be verified in polynomial time by a deterministic Turing machine.

Report an error in this question

Complexity & OptimizationEasy

Q9. What is time-space tradeoff?

  1. A.Time complexity cannot affect space complexity
  2. B.Time and space are always equal in measure
  3. C.Using more time to save space or vice versa✓ Correct
  4. D.A method to reduce both time and space simultaneously

Explanation

A time-space tradeoff means that an algorithm can use more memory to run faster, or use less memory at the cost of running slower.

Report an error in this question

Complexity & OptimizationEasy

Q10. What is the best time complexity achievable for comparison-based sorting?

  1. A.O(log n)
  2. B.O(n log n)✓ Correct
  3. C.O(n)
  4. D.O(n^2)

Explanation

The lower bound for any comparison-based sorting algorithm is Ω(n log n), proven using the decision tree model.

Report an error in this question

Complexity & OptimizationEasy

Q11. What does 'in-place algorithm' mean?

  1. A.An algorithm that runs at a specific location
  2. B.An algorithm using only constant extra space✓ Correct
  3. C.An algorithm that cannot be relocated in memory
  4. D.An algorithm that only sorts data in place

Explanation

An in-place algorithm uses only O(1) or O(log n) extra space beyond the input, modifying the input directly rather than using auxiliary data structures.

Report an error in this question

Complexity & OptimizationEasy

Q12. What does P stand for in computational complexity?

  1. A.Problems solvable in polynomial time✓ Correct
  2. B.Prime number problems class
  3. C.Probability problems class
  4. D.Parallel problems class

Explanation

P is the class of decision problems that can be solved by a deterministic Turing machine in polynomial time.

Report an error in this question

Complexity & OptimizationEasy

Q13. What is the time complexity of accessing an element in a hash table on average?

  1. A.O(n^2)
  2. B.O(log n)
  3. C.O(1)✓ Correct
  4. D.O(n)

Explanation

Hash tables provide O(1) average-case time for access, insertion, and deletion with a good hash function.

Report an error in this question

Complexity & OptimizationMedium

Q14. What is memoization's space-time tradeoff?

  1. A.It uses no extra space at all
  2. B.It uses extra space to avoid redundant computation✓ Correct
  3. C.It increases time to save storage space
  4. D.It reduces both space and time simultaneously

Explanation

Memoization trades extra memory (to store computed results) for faster execution (by looking up previously computed results instead of recomputing them).

Report an error in this question

Complexity & OptimizationHard

Q15. What is the complexity class PSPACE?

  1. A.Problems solvable using polynomial space amount✓ Correct
  2. B.Problems requiring exponential space to solve
  3. C.Problems solvable in constant space only
  4. D.Problems with no space requirement at all

Explanation

PSPACE is the class of problems solvable by a Turing machine using a polynomial amount of space. P ⊆ NP ⊆ PSPACE.

Report an error in this question

Complexity & OptimizationMedium

Q16. What is loop unrolling?

  1. A.Removing all loops from the source code base entirely
  2. B.Making loops run in the reverse backward execution order
  3. C.Executing multiple iterations per loop cycle to reduce overhead✓ Correct
  4. D.Converting all iterative loops to recursion-based calls

Explanation

Loop unrolling is a compiler optimization that reduces loop overhead by executing the body of the loop multiple times per iteration, reducing the number of branch instructions.

Report an error in this question

Complexity & OptimizationMedium

Q17. Why is O(n log n) considered efficient for sorting?

  1. A.It works only for small input sizes efficiently
  2. B.It uses the least memory of all algorithms
  3. C.It matches the comparison-based sorting lower bound✓ Correct
  4. D.It is the fastest possible for all sorting

Explanation

O(n log n) is optimal for comparison-based sorting algorithms, as proven by the Ω(n log n) lower bound from decision tree analysis.

Report an error in this question

Complexity & OptimizationMedium

Q18. What is the difference between best case, worst case, and average case complexity?

  1. A.Best is minimum time, worst is maximum, average is expected✓ Correct
  2. B.Worst case is purely theoretical and never practical
  3. C.They are always the same value for any algorithm
  4. D.Best case only applies to small input sizes

Explanation

Best case is the minimum time for any input of size n, worst case is the maximum, and average case is the expected time averaged over all possible inputs.

Report an error in this question

Complexity & OptimizationMedium

Q19. What is cache-friendly code?

  1. A.Code with no memory access at all
  2. B.Code that runs entirely in cache memory
  3. C.Code that uses caching library APIs
  4. D.Code that maximizes CPU cache hit rates✓ Correct

Explanation

Cache-friendly code accesses memory sequentially or in patterns that maximize spatial and temporal locality, reducing cache misses and improving performance.

Report an error in this question

Complexity & OptimizationMedium

Q20. What is tail recursion optimization?

  1. A.Adding a tail data structure to the recursion stack
  2. B.Removing all recursive calls from the entire program
  3. C.Making recursive call the last operation for iteration optimization✓ Correct
  4. D.Making the recursion run in reverse backward order

Explanation

Tail recursion optimization converts a recursive function where the recursive call is the last operation into an iterative loop, eliminating stack overhead.

Report an error in this question

Complexity & OptimizationMedium

Q21. What is a polynomial reduction?

  1. A.Reducing the degree of a polynomial expression
  2. B.Transforming one problem into another in polynomial time✓ Correct
  3. C.Reducing the time complexity of an algorithm
  4. D.Simplifying an algorithm's code implementation

Explanation

A polynomial reduction transforms an instance of problem A into an instance of problem B in polynomial time, used to prove that B is at least as hard as A.

Report an error in this question

Complexity & OptimizationHard

Q22. What is Cook's theorem?

  1. A.P equals NP has been conclusively proven
  2. B.Every NP problem is fundamentally unsolvable
  3. C.Every problem is solvable in polynomial time
  4. D.The Boolean satisfiability problem (SAT) is NP-complete✓ Correct

Explanation

Cook's theorem (1971) proves that the Boolean satisfiability problem (SAT) is NP-complete, establishing the first known NP-complete problem.

Report an error in this question

Complexity & OptimizationHard

Q23. What is the approximation ratio of the 2-approximation algorithm for vertex cover?

  1. A.The solution is at most twice the optimal✓ Correct
  2. B.The solution is at most 1.5 times optimal
  3. C.The solution is at most 3 times the optimal
  4. D.The solution always equals the optimal exactly

Explanation

The greedy 2-approximation algorithm for vertex cover guarantees a solution at most twice the size of the optimal solution.

Report an error in this question

Complexity & OptimizationHard

Q24. What is the vertex cover problem?

  1. A.Coloring all vertices with minimum colors
  2. B.Finding all connected vertices in a graph
  3. C.Finding smallest vertex set covering all edges✓ Correct
  4. D.Covering all vertices with color assignments

Explanation

The vertex cover problem asks for the smallest set of vertices that covers all edges (every edge has at least one endpoint in the set). It is NP-complete.

Report an error in this question

Complexity & OptimizationHard

Q25. What is the difference between a decision problem and an optimization problem?

  1. A.Decision has yes/no answer; optimization seeks best solution✓ Correct
  2. B.They are exactly the same type of problem
  3. C.Optimization problems are always solvable in P
  4. D.Decision problems are always computationally harder

Explanation

A decision problem asks a yes/no question (e.g., 'Is there a path shorter than k?'). An optimization problem seeks the optimal solution (e.g., 'What is the shortest path?').

Report an error in this question

Complexity & OptimizationHard

Q26. What is pseudo-polynomial time?

  1. A.An algorithm that pretends to be efficient
  2. B.Time polynomial in input value rather than input size✓ Correct
  3. C.False polynomial time that does not exist
  4. D.The same as polynomial time in all cases

Explanation

A pseudo-polynomial algorithm runs in time polynomial in the value of the input (e.g., O(nW) for knapsack) but not in the size (number of bits) of the input.

Report an error in this question

Complexity & OptimizationHard

Q27. What is the 3-SAT problem?

  1. A.A Boolean satisfiability problem with 3 literals per clause✓ Correct
  2. B.A problem with exactly 3 valid solutions
  3. C.A sorting problem with 3 distinct elements
  4. D.Satisfying exactly 3 linear equations

Explanation

3-SAT is a special case of SAT where the Boolean formula is in CNF and each clause has exactly 3 literals. It is NP-complete and often used for reductions.

Report an error in this question

Complexity & OptimizationHard

Q28. What is the class co-NP?

  1. A.The class whose complement problems are in NP✓ Correct
  2. B.The complement of NP problems
  3. C.Problems that are harder than NP class
  4. D.Problems that are not in NP at all

Explanation

co-NP contains problems whose complement (negation) is in NP. For example, 'is this formula unsatisfiable?' is in co-NP because 'is it satisfiable?' is in NP.

Report an error in this question

Complexity & OptimizationHard

Q29. What is the time hierarchy theorem?

  1. A.All problems can be solved in the same time
  2. B.Time complexity is always fixed and unchanging
  3. C.More time allows a Turing machine to solve more problems✓ Correct
  4. D.There is no hierarchy in time complexity classes

Explanation

The time hierarchy theorem states that given more time, Turing machines can solve more problems. Specifically, DTIME(f(n)) is strictly contained in DTIME(f(n) × log f(n)) for reasonable f.

Report an error in this question

Complexity & OptimizationHard

Q30. What is a parameterized algorithm?

  1. A.An algorithm that dynamically changes its parameters at runtime
  2. B.An algorithm whose complexity depends on input size and a fixed parameter✓ Correct
  3. C.A tunable sorting algorithm that uses an adjustable pivot element
  4. D.An algorithm that has many user-tunable parameter values

Explanation

Parameterized algorithms measure complexity as f(k) × n^c, where k is a parameter. A problem is FPT if it can be solved in time f(k) × n^O(1), isolating the exponential part to the parameter k.

Report an error in this question

More Data Structures & Algorithms Topics

Foundations of DS & Algorithms

Practice MCQs with explanations

Linear Data Structures

Practice MCQs with explanations

Non-Linear Data Structures

Practice MCQs with explanations

Searching Algorithms

Practice MCQs with explanations

Sorting Algorithms

Practice MCQs with explanations

Hashing

Practice MCQs with explanations

Ready to test yourself on Complexity & Optimization?

Take a timed quiz drawn from 210+ questions on this topic. No signup required — your progress saves in your browser.

Start Complexity & Optimization Quiz