Complexity Analysis MCQs, Set 1 of 1
Q1 / 14
Q1. What does Big-O notation describe?
- A.The exact running time
- B.An upper bound on the growth rate(correct answer)
- C.The memory address of data
- D.The number of CPU cores used
Big-O bounds how fast cost can grow as input size grows.
Q2. Which of these grows fastest as n increases?
- A.O(n log n)
- B.O(n²)
- C.O(2^n)(correct answer)
- D.O(n³)
Exponential growth eventually beats any polynomial.
Q3. What is the time complexity of two nested loops that each run n times?
- A.O(n)
- B.O(2n)
- C.O(n²)(correct answer)
- D.O(log n)
The inner body runs n × n times.
Q4. A loop where i doubles each time (1, 2, 4, 8, ... up to n) runs how many times?
- A.O(n)
- B.O(log n)(correct answer)
- C.O(n²)
- D.O(1)
Doubling reaches n after about log2(n) steps.
Q5. O(2n + 5) simplifies to:
- A.O(2n)
- B.O(n)(correct answer)
- C.O(5)
- D.O(n + 5)
Constant factors and lower-order terms are dropped.
Q6. Which notation gives a tight bound (both upper and lower)?
- A.Big-O
- B.Big-Omega
- C.Big-Theta(correct answer)
- D.Little-o
Big-Theta means the growth is bounded above and below by the same function.
Q7. The recurrence T(n) = 2T(n/2) + n solves to:
- A.O(n)
- B.O(n log n)(correct answer)
- C.O(n²)
- D.O(log n)
There are log n levels, each doing O(n) work (the merge sort recurrence).
Q8. What is the time complexity of the naive recursive Fibonacci function?
- A.O(n)
- B.O(n log n)
- C.O(n²)
- D.O(2^n)(correct answer)
Each call branches into two more calls, giving exponential growth.
Q9. Space complexity measures:
- A.How long a program takes to run
- B.How much memory an algorithm needs as the input grows(correct answer)
- C.The size of the source code
- D.The number of function names
It counts extra memory as a function of input size.
Q10. Reading an array element by index, pushing to a stack, and an average hash table lookup all take:
- A.O(1)(correct answer)
- B.O(log n)
- C.O(n)
- D.O(n²)
Each is a constant-time operation.
Q11. Problems that a deterministic algorithm can solve in polynomial time belong to class:
- A.P(correct answer)
- B.NP-complete
- C.Undecidable
- D.EXPTIME-complete
P is the class of problems solvable in polynomial time.
Q12. Which of these problems is NP-complete?
- A.Sorting an array
- B.Boolean satisfiability (SAT)(correct answer)
- C.Shortest path with Dijkstra
- D.Binary search
SAT was the first problem proved NP-complete (Cook-Levin theorem).
Q13. An O(n²) algorithm takes 1 second for n = 1000. Roughly how long for n = 2000?
- A.2 seconds
- B.4 seconds(correct answer)
- C.8 seconds
- D.1 second
Doubling n multiplies n² by 4.
Q14. Dynamic programming improves on naive recursion mainly by:
- A.Using more threads
- B.Storing results of overlapping subproblems(correct answer)
- C.Sorting the input first
- D.Avoiding loops
Each subproblem is solved once and reused (memoization or tabulation).