Q.1 What does Big-O notation represent in algorithm analysis?
Best-case complexity
Average-case complexity
Upper bound of growth rate
Exact running time
Explanation - Big-O gives an upper bound on the growth rate of an algorithm's running time, ensuring performance won't exceed this limit for large inputs.
Correct answer is: Upper bound of growth rate
Q.2 Which notation provides a tight bound on an algorithm’s growth?
Big-O
Big-Theta
Big-Omega
Little-o
Explanation - Big-Theta gives a tight bound, meaning it describes both the upper and lower asymptotic bounds.
Correct answer is: Big-Theta
Q.3 What does Big-Omega notation signify?
Upper bound
Lower bound
Average case
Exact time
Explanation - Big-Omega represents the asymptotic lower bound of an algorithm’s growth rate.
Correct answer is: Lower bound
Q.4 If an algorithm has time complexity O(n^2), which of the following is true?
It always takes n^2 steps
It never takes more than n^2 steps
It grows at most proportional to n^2
It grows exactly like n^2
Explanation - Big-O indicates an upper bound; the runtime will not exceed a constant times n^2.
Correct answer is: It grows at most proportional to n^2
Q.5 Which of the following is the most efficient time complexity?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - Constant time O(1) means execution takes the same time regardless of input size, making it the most efficient.
Correct answer is: O(1)
Q.6 For binary search, the time complexity is:
O(n)
O(log n)
O(n log n)
O(1)
Explanation - Binary search halves the search space at each step, leading to logarithmic complexity O(log n).
Correct answer is: O(log n)
Q.7 Which notation is best suited for describing the worst-case running time?
Big-O
Big-Theta
Big-Omega
Little-o
Explanation - Big-O is most commonly used to describe worst-case scenarios as it provides an upper bound.
Correct answer is: Big-O
Q.8 What is the time complexity of traversing a linked list of size n?
O(1)
O(log n)
O(n)
O(n^2)
Explanation - To traverse the entire linked list, each element must be visited once, leading to O(n) complexity.
Correct answer is: O(n)
Q.9 If T(n) = 3n^2 + 5n + 10, the Big-O complexity is:
O(1)
O(n)
O(n^2)
O(n^3)
Explanation - For Big-O, the highest-order term dominates, so the complexity is O(n^2).
Correct answer is: O(n^2)
Q.10 Which complexity class represents algorithms that run in exponential time?
O(n)
O(log n)
O(2^n)
O(n log n)
Explanation - Exponential algorithms have growth like 2^n, making them highly inefficient for large inputs.
Correct answer is: O(2^n)
Q.11 The best-case time complexity of QuickSort is:
O(n)
O(n log n)
O(n^2)
O(log n)
Explanation - QuickSort achieves O(n log n) when partitions are balanced at each step.
Correct answer is: O(n log n)
Q.12 What is the Big-O of inserting an element at the end of an array (without resizing)?
O(1)
O(n)
O(log n)
O(n^2)
Explanation - Appending to the end of an array (without resizing) takes constant time.
Correct answer is: O(1)
Q.13 Which of the following is asymptotically slower?
O(n)
O(n log n)
O(2^n)
O(log n)
Explanation - Exponential time O(2^n) grows much faster than polynomial or logarithmic time.
Correct answer is: O(2^n)
Q.14 If an algorithm has Ω(n), it means:
It always takes n steps
It takes at least proportional to n steps
It never exceeds n steps
It runs in constant time
Explanation - Big-Omega indicates a lower bound, so the algorithm takes at least proportional to n time.
Correct answer is: It takes at least proportional to n steps
Q.15 Which is faster asymptotically: O(n log n) or O(n^2)?
O(n log n)
O(n^2)
Both are equal
Depends on input
Explanation - For large n, n log n grows slower than n^2, making it more efficient.
Correct answer is: O(n log n)
Q.16 What does the term 'asymptotic' mean in complexity analysis?
Exact values
Behavior for small inputs
Behavior for large inputs
Worst-case only
Explanation - Asymptotic analysis studies how algorithms behave as input size tends toward infinity.
Correct answer is: Behavior for large inputs
Q.17 Which notation describes the exact asymptotic behavior of an algorithm?
Big-O
Big-Theta
Big-Omega
Little-o
Explanation - Big-Theta describes the exact asymptotic behavior by bounding both upper and lower limits.
Correct answer is: Big-Theta
Q.18 What is the time complexity of linear search in the worst case?
O(1)
O(n)
O(log n)
O(n^2)
Explanation - Linear search may require scanning the entire list, resulting in O(n) in the worst case.
Correct answer is: O(n)
Q.19 Which of these notations can represent the best-case scenario?
Big-O
Big-Theta
Big-Omega
All of the above
Explanation - Big-Omega is generally used for best-case lower bound analysis.
Correct answer is: Big-Omega
Q.20 The recurrence T(n) = 2T(n/2) + O(n) corresponds to which algorithm?
Merge Sort
Binary Search
Linear Search
Selection Sort
Explanation - This recurrence describes Merge Sort’s divide-and-conquer method, giving O(n log n).
Correct answer is: Merge Sort
Q.21 Which is the slowest among the following?
O(n)
O(log n)
O(1)
O(n^3)
Explanation - Cubic time grows much faster than linear, logarithmic, or constant time.
Correct answer is: O(n^3)
Q.22 If T(n) = n^2 + log n, what is the Big-Theta?
Θ(log n)
Θ(n)
Θ(n^2)
Θ(n log n)
Explanation - In Big-Theta, the dominant term n^2 defines the exact bound.
Correct answer is: Θ(n^2)
Q.23 Which complexity class is usually considered infeasible?
O(n)
O(n log n)
O(2^n)
O(log n)
Explanation - Exponential time algorithms are infeasible for large inputs as they grow too fast.
Correct answer is: O(2^n)
Q.24 Which of these is NOT asymptotic notation?
Big-O
Big-Theta
Little-o
Big-Pi
Explanation - Big-Pi is not an asymptotic notation; only Big-O, Big-Theta, Big-Omega, and related exist.
Correct answer is: Big-Pi
Q.25 If an algorithm runs in O(log n), doubling input size increases time by:
Constant
Double
Square
Depends on implementation
Explanation - Logarithmic growth increases very slowly, so doubling n adds only a constant factor.
Correct answer is: Constant