Asymptotic notation looks like three symbols to memorise, but exams test the gaps between their definitions. Big O is an upper bound, Omega is a lower bound, and Theta gives both. These 12 solved MCQs come from KnowledgeGate's published question bank, which carries about 40 questions on this subtopic, and nine are tagged as previous-year questions. Attempt each first; the nine PYQs link to their solved pages, while the three concept questions sit in the Algorithms learn module.
Warm-up: what each notation actually claims
Formally, f(n) = O(g(n)) if constants c > 0 and n0 exist such that f(n) <= c g(n) for every n >= n0. Omega reverses the bound, while Theta requires both. Use Data Structures MCQs for related growth-rate practice.
Q1. Big O meaning
TPSC Assistant Programmer 2025 asks: What does the term "Big-O notation" describe?
(a) The exact running time of an algorithm
(b) The space required by an algorithm
(c) The upper bound of an algorithm's time complexity
(d) The number of operations executed by an algorithm
Answer: (c). Big O bounds growth from above. It is not an exact time, a space measure specifically, or an operation count.
Q2. Function or notation?
Which of the following is not an Asymptotic Notation?
(a) O(n)
(b) Θ(n)
(c) Ω(n)
(d) n²
Answer: (d). n² is a function. O(n²), Θ(n²), and Ω(n²) wrap a function in a claim about growth.
Q3. The lower bound
DSSSB TGT 2021 asks: Which of the following asymptotic notation is used to provide lower boundary constraints?
(a) O
(b) Θ
(c) Ω
(d) ω
Answer: (c). Ω is the lower bound. The strict lower bound ω is the trap; O is upper and Θ is tight.
Theta means both bounds at once
Theta(g) means O(g) and Ω(g) together. Do not translate O into “worst case” or Theta into “average case”. Those cases are different functions being bounded.
Q4. Reading Θ(n)
Beltron Programmer 2025 Shift-3 asks: If an algorithm's time complexity is Θ(n), what does that imply?
(a) Only lower bound is n
(b) Only upper bound is n
(c) Both upper and lower bounds are n
(d) Time complexity cannot be determined
Answer: (c). Being O(n) and Ω(n) pins the function to linear growth up to constant factors.
Q5. A negative-question drill
Which of the following is true for both Big O and Big Omega notation?
(a) They provide upper bound
(b) They provide lower bound
(c) They provide tight bound
(d) None of the above
Answer: (d). O is upper, Ω is lower, and Θ is tight. None of the first three describes both O and Ω.
Dropping lower-order terms, the right way
The fastest-growing term determines a sum's tight class, once the bound is justified.
Q6. Proving the dominant term
If f(n) = n² + 3n + 4, then which of the following is correct?
(a) f(n) = O(n³)
(b) f(n) = O(n²)
(c) f(n) = O(n)
(d) f(n) = O(1)
Answer: (b). For n >= 4,
n² - 3n - 4 = (n - 4)(n + 1) >= 0.
Therefore, 3n + 4 <= n².
So f(n) = n² + 3n + 4 <= 2n².
Thus c = 2 and n0 = 4 prove O(n²). At n = 4, 3(4) + 4 = 16 = 4², and f(4) = 16 + 12 + 4 = 32 = 2(4²). Option (a) is also a loose upper bound, but (b) is the tightest listed answer.
Q7. Finding the dominant term
HPSC 2015 asks: Big O estimate for the function f(x) = x log(2x) + x³ + 5x² + 10 is:
(a) O(x log x)
(b) O(x³)
(c) O(x²)
(d) O(x log(2x))
(e) Question not attempted
Answer: (b). x³ dominates x log(2x), 5x², and 10, so the sum is O(x³). Option (e) comes from the exam answer sheet.
Combining modules and chaining bounds
Sequential costs add, with h(n) + g(n) = Θ(max(h(n), g(n))) for nonnegative runtimes. Nested work multiplies, and Big O is transitive. For example, n² + n = Θ(n²).
Q8. Two sequential modules
UGC NET June 2014 asks: An algorithm is made up of 2 modules M1 and M2. If time complexity of modules M1 and M2 are h(n) and g(n) respectively, the time complexity of the algorithm is:
(a) min(h(n), g(n))
(b) max(h(n), g(n))
(c) h(n) + g(n)
(d) h(n) * g(n)
Answer: (b). The literal cost is h(n) + g(n), but its class is Θ(max(h(n), g(n))), expressed by (b). Multiplication applies to nested execution.
Q9. Following a chain of bounds
GATE 2004, Information Technology paper asks: Let f(n), g(n) and h(n) be functions defined for positive integers such that f(n) = O(g(n)), g(n) ≠ O(f(n)), g(n) = O(h(n)), and h(n) = O(g(n)). Which one of the following statements is FALSE?
(a) f(n) + g(n) = O(h(n) + h(n))
(b) f(n) = O(h(n))
(c) f(n)h(n) ≠ O(f(n))
(d) f(n)h(n) ≠ O(g(n)h(n))
Answer: (d). The premises make g and h Θ-equivalent, with g beyond f. Transitivity proves (b), while f + g = O(g) = O(h) proves (a). In the intended positive growth setting, unbounded h makes (c) true. Multiplying f(n) <= c g(n) by positive h(n) gives f(n)h(n) <= c g(n)h(n). Therefore f(n)h(n) is O(g(n)h(n)), making (d) false.
Properties the little notations test
The symbols o and ω are the strict versions of O and Ω. Each is transitive, and f = O(g) means g = Ω(f). The GATE question types primer separates MCQ, MSQ, and NAT rules.
Q10. Transitivity of little-o
UGC NET June 2022 asks: Assume that f(n) and g(n) are asymptotically positive. Which of the following is correct?
(a) f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = ω(h(n))
(b) f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⇒ f(n) = O(h(n))
(c) f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n))
(d) f(n) = ω(g(n)) and g(n) = ω(h(n)) ⇒ f(n) = Ω(h(n))
Recorded answer: (c). Since f/g and g/h tend to 0, f/h = (f/g)(g/h) tends to 0. Option (a) fails for f = g = h = n, and (b) reverses its conclusion.
However, standard definitions also make (d) true: ω is transitive, and f = ω(h) implies f = Ω(h). The key records (c), but this single-answer item is not unique.
Q11. Reading growth direction correctly
UGC NET 2023 asks: Given below are two statements:
Statement I: If f and g are two functions and f = O(g) but g ≠ O(f), we say that the growth rate of g is smaller than that of f.
Statement II: The class of all decision problems decided by a Turing Machine in exponential time, that is O(2^k), k being a constant.
(a) Both Statement I and Statement II are correct
(b) Both Statement I and Statement II are incorrect
(c) Statement I is correct but Statement II is incorrect
(d) Statement I is incorrect but Statement II is correct
Answer: (b). Statement I reverses the direction: g grows faster than f. In Statement II, fixed k makes 2^k constant. Exponential time instead depends exponentially on input size, as in O(2^n). Both are incorrect.
Worst case vs average case, the classic
Worst-case W(n) and average-case A(n) are different functions. The average cannot exceed the maximum, so A(n) <= W(n).
Q12. The relation that is always true
GATE 2012 asks: Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?
(a) A(n) = Ω(W(n))
(b) A(n) = Θ(W(n))
(c) A(n) = O(W(n))
(d) A(n) = o(W(n))
Answer: (c). Every input takes at most W(n), so the average does too. With c = 1, A(n) = O(W(n)). Quicksort disproves (a) and (b): its average is Θ(n log n) and worst case is Θ(n²). Algorithms with identical time on every same-sized input disprove (d).
The short version and your next step
O is an upper bound, Ω is a lower bound, and Θ gives both.
o and ω make the corresponding bounds strict.
Sequential costs add and reduce to the largest term asymptotically; nested costs usually multiply.
Transitivity lets you chain bounds.
A(n) = O(W(n)) is the only relation here that holds for every algorithm.
KnowledgeGate carries about 40 published questions on Asymptotic Notations alone. Every PYQ above sits solved inside GATE Guidance by Sanchit Sir, and you can browse the wider set of GATE CS preparation options before choosing your next practice block.
