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. Nine of the twelve questions below are previous-year questions, drawn from GATE, UGC NET, DSSSB, HPSC, TPSC and Beltron papers, and each of those links to its fully solved page. Attempt every question before you read the explanation under it. The rest of the practice set sits 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 inequality, and Theta demands both at once. Notice what the definition does not say: nothing about worst case, nothing about a particular input. The same growth-rate reasoning decides the complexity questions in Data Structures MCQs.
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. An exact running time (a) and a count of operations (d) are quantities, not bounds. Big O can bound space as well, but (b) drops the bounding idea and names the resource only, so (c) is the one statement that describes what the notation asserts.
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 sets the class of a sum. Exams rarely stop at that reflex though: they want the constant c and the threshold n0 that make the inequality true, and they list a looser correct bound next to the tightest one to see which you pick.
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))
Answer: (b). Divide the whole function by x³ and watch the other terms vanish: 5x²/x³ = 5/x, x log(2x)/x³ = log(2x)/x², and 10/x³ all tend to 0, so the cube sets the class. Options (a) and (d) are the same bound written two ways, since log(2x) = log 2 + log x, and both undershoot the cubic term, as does (c).
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.
Little-o, little-omega, and the direction of a bound
The symbols o and ω are the strict versions of O and Ω: f = o(g) means f/g tends to 0, so f is beaten outright rather than merely matched. Both are transitive, and f = O(g) is the same claim as g = Ω(f) read backwards, which is the step candidates most often invert. The first question below is a single-answer item where a second option is also defensible, the exact MCQ-versus-MSQ boundary the GATE question types primer sets out.
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))
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.
Look hard at (d) before moving on, because by the standard definitions it is true as well: ω is transitive, so f = ω(g) and g = ω(h) give f = ω(h), and ω is strictly stronger than Ω. The official key marks only (c), so mark (c) if this item reappears, but treat it as a reminder that a single-answer paper can still carry two sound options.
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.
Asymptotic notations alone carry about 40 practice questions on KnowledgeGate, so the twelve here are an entry point rather than the whole set. Every previous-year question above sits solved inside GATE Guidance by Sanchit Sir, and GATE CS preparation options shows where algorithm analysis sits in a full syllabus plan.
