Asymptotic Notations

Purpose

• Asymptotic notation describes an algorithm's growth rate as input size n → infinity, ignoring constants and lower-order terms — the standard language for comparing algorithm efficiency

Functions (Uses) of Asymptotic Notation

A common standalone FPSC theory question is simply "What are the functions/uses of asymptotic notation?" — these are the concrete jobs it does for algorithm analysis, beyond the one-line definition above:

1. Hardware/implementation independence — expresses running time purely as a function of input size n (number of basic operations), so two algorithms can be compared without depending on CPU speed, compiler, or programming language.
2. Comparing algorithms objectively — gives a common scale (O(n) vs O(n²) vs O(log n)) to decide which of several algorithms solving the same problem scales better, without running or timing any of them.
3. Predicting scalability / behavior for large n — the whole point of "asymptotic" is behavior as n → ∞; it tells you how an algorithm will perform on large real-world inputs, not just the small test cases you can actually measure.
4. Abstracting away constants and lower-order terms — real running time is messy (T(n) = 3n² + 5n + 2), but only the dominant term matters for large n, so notation strips away implementation noise and leaves the essential growth behavior.
5. Classifying algorithms into complexity classes — buckets every algorithm into a small set of standard classes (constant, logarithmic, linear, linearithmic, quadratic, exponential, ...), making it possible to reason about entire families of problems at once (e.g. "all comparison sorts are at best O(n log n)").
6. Characterizing best/worst/average-case behavior precisely — O, Ω, and Θ let you state exactly which case (upper bound, lower bound, or tight bound) a claim about an algorithm refers to, avoiding ambiguity in specifications and proofs.
7. Guiding algorithm design and optimization decisions — by exposing which part of an algorithm dominates its growth (e.g. a nested loop vs. a single pass), it tells a designer exactly where optimization effort will actually pay off.
8. Providing a rigorous mathematical foundation for proofs — the formal c, n₀ definitions turn "this algorithm is efficient" from a vague claim into something that can be proven, which is exactly what the properties table above and the worked c/n₀ proofs below rely on.

Exam angle: if a question asks "what is the significance/function/purpose of asymptotic notation" as a short-note or MCQ-justification item, points 1–3 (hardware independence, comparability, scalability prediction) are the core answer FPSC examiners look for; points 4–8 are good supporting detail for an 8-mark detailed-note version of the same question.

The Three Notations

Properties of Asymptotic Notations

These formal properties let you manipulate and combine O/Ω/Θ expressions algebraically — both a common standalone FPSC theory question ("state the properties of Big-O notation") and the justification for shortcuts like "just add the biggest term" used throughout this page.

Worked mini-example (transpose symmetry in action): earlier on this page we showed 5n+50 is NOT O(log₁₀n), and concluded instead that log₁₀n = O(5n+50). Transpose symmetry says this is the same fact stated two ways: since f(n)=5n+50 is NOT O(g(n))=O(log₁₀n), by the growth-rate hierarchy the true relationship is f(n) = Ω(g(n)) — and g(n) = O(f(n)) follows directly.

Little-o and Little-Omega — the STRICT versions (a favorite MCQ trap)

MCQ Trap: "n² = O(n²)" is TRUE (Big-O allows equal growth rates), but "n² = o(n²)" is FALSE (little-o strictly forbids equal growth — a function is never "strictly slower" than itself). This exact O-vs-o substitution is a classic trick option in FPSC MCQs.

---

Step-by-Step: Counting Operations to Build T(n)

Before you can prove a Big-O bound, you first need T(n) — the actual function describing an algorithm's running time. The standard technique is the step-count (operation-count) method: assign a constant cost to each primitive operation, count how many times each line actually executes, and sum them.

Method — 4 steps:

1. List every statement in the algorithm/code.
2. Assign a cost to each — a simple assignment, comparison, or arithmetic operation is usually counted as 1 step (constant time).
3. Count executions — a statement inside a loop that runs n times executes n times; the loop test itself runs one extra time (the final "false" check that exits the loop).
4. Sum everything into T(n), then keep only the dominant term (drop constants and lower-order terms) to name the Big-O class.

Worked Example: Step-Counting the Sum of an Array

int sum(int arr[], int n) {
    int s = 0;                      // Line A
    for (int i = 0; i < n; i++) {   // Line B
        s = s + arr[i];              // Line C
    }
    return s;                       // Line D
}

Total:

$$T(n) = 1 + 1 + (n+1) + n + n + 1 = 3n + 4$$

Simplify to Big-O: drop the coefficient (3) and the constant (+4) — only the fastest-growing term matters: $T(n) = O(n)$.

You can now formally prove this with the c, n₀ method below: try c=4:

$$3n+4 \leq 4n \iff 4 \leq n$$

so n₀ = 4 (verify: at n=4, LHS=16, RHS=16 ✓).

A Second Example — Nested Loop (shows where n² comes from)

for (int i = 0; i < n; i++) {        // outer loop: runs n times
    for (int j = 0; j < n; j++) {    // inner loop: runs n times, for EACH outer iteration
        cout << i * j;                // 1 step, executed n × n times total
    }
}

The innermost statement runs n times for every one of the n outer iterations → n × n = n² total executions. This is exactly why nested loops over the same range give O(n²) — each additional nested loop over n multiplies the step count by another factor of n (three nested loops → O(n³), and so on).

Exam angle: FPSC step-count questions typically give a short code/pseudocode snippet and ask you to either (a) derive T(n) line-by-line like the table above, or (b) just name the final Big-O class. Always check loop bounds carefully — a loop running n/2 times, or a bound depending on another loop variable (like for j = i to n), changes the count and is a common place examiners test whether you're really counting or just guessing.

A Third, Simple Example — Loop + Condition (the 5-step template)

Use this exact 5-step template for any "analyze this code" question:

1. Write the algorithm.
2. Count how many times each statement executes.
3. Form the running-time equation T(n).
4. Keep only the highest-order term to determine Big-O.
5. If asked, prove it by finding c and n₀.

Q: Count how many even numbers are in an array of size n. Analyze its time complexity.

Step 1 — Write the algorithm:

int countEven(int arr[], int n) {
    int count = 0;                      // A
    for (int i = 0; i < n; i++) {       // B
        if (arr[i] % 2 == 0) {          // C  (the condition)
            count++;                     // D  (runs only when C is true)
        }
    }
    return count;                       // E
}

Step 2 — Count how many times each statement executes (worst case: every element is even, so the if body always runs):

Key point on conditions: an if's condition (line C) always executes once per loop pass, no matter which branch is taken — only the code inside the if body (line D) is conditional on the outcome. Count these as two separate rows, exactly like above.

Step 3 — Form T(n) (worst case):

$$T(n) = \underbrace{1}_{A} + \underbrace{1}_{B\text{-init}} + \underbrace{(n+1)}_{B\text{-test}} + \underbrace{n}_{B\text{-update}} + \underbrace{n}_{C} + \underbrace{n}_{D} + \underbrace{1}_{E} = 4n + 4$$

(Best case — no evens, line D contributes 0 — gives $T(n) = 3n+4$ instead.)

Step 4 — Keep only the highest-order term:

Both 4n + 4 (worst case) and 3n + 4 (best case) have n as their highest-order term — drop the coefficients (4 or 3) and the constant (+4):

T(n) = O(n) in both cases.

Key reasoning point: the if condition changes the exact T(n) (4n+4 vs 3n+4) but not the Big-O class — it's still just one pass through the array either way. A condition only changes the complexity class itself when it causes extra looping/recursion (e.g. a nested loop that only runs conditionally), not when it merely skips one O(1) statement sometimes.

Step 5 — Prove it by finding c and n₀ (using the worst case, T(n) = 4n+4):

Need $4n + 4 \leq c\cdot n$. Try c = 5:

$$4n + 4 \leq 5n \iff 4 \leq n$$

So n₀ = 4. Verify at n=4: LHS = 4(4)+4 = 20, RHS = 5(4) = 20 → 20 ≤ 20 ✓. At n=10: LHS=44, RHS=50 ✓.

Conclusion: $T(n) = 4n+4 = O(n)$, confirmed with c=5, n₀=4.

---

How to Formally Prove Big-O (finding c and n₀)

Definition: $f(n) = O(g(n))$ means there exist positive constants c and n₀ such that:

$$0 \leq f(n) \leq c\cdot g(n) \quad \text{for all } n \geq n_0$$

Method — 4 steps (memorize this template):

1. Set up the inequality you need to satisfy: f(n) ≤ c·g(n).
2. Choose a convenient c — any value greater than or equal to the leading coefficient of f(n)'s dominant term usually works. Pick a small, clean number.
3. Solve the inequality for n — whatever threshold falls out is your n₀.
4. Verify by substituting n = n₀ (and one larger value) back into the original inequality.

(c, n₀) pairs are NOT unique. Infinitely many valid pairs exist for the same proof — examiners only need ONE correctly derived and verified pair, not "the" answer.

Worked Example: Prove 5n + 50 = O(n)

Q: Prove that f(n) = 5n + 50 is O(n). Find values of c and n₀ satisfying the definition.

Step 1 — Set up the inequality:

Need: $5n + 50 \leq c\cdot n$ for all $n \geq n_0$.

Step 2 — Choose a convenient c:

Try c = 6 (any value greater than 5, the coefficient of n, works — 6 is the simplest choice):

$5n + 50 \leq 6n$

Step 3 — Solve for n:

$$5n + 50 \leq 6n \;\implies\; 50 \leq 6n - 5n \;\implies\; 50 \leq n$$

So $n \geq 50$ → n₀ = 50.

Step 4 — Verify:

• At n = 50: LHS = 5(50)+50 = 300, RHS = 6(50) = 300 → 300 ≤ 300 ✓
• At n = 100: LHS = 5(100)+50 = 550, RHS = 6(100) = 600 → 550 ≤ 600 ✓

Conclusion: Since c = 6 and n₀ = 50 satisfy $5n+50 \leq 6n$ for all $n \geq 50$, by definition $5n + 50 = O(n)$. ∎

Alternative valid pair (proves c, n₀ aren't unique): c = 7, n₀ = 25 also works:

$$5n+50 \leq 7n \implies 50 \leq 2n \implies n \geq 25$$

Check at n=25: LHS=175, RHS=175 ✓.

MCQ/Exam Trap: don't confuse this with proving Ω or Θ:

• Ω (lower bound): need f(n) ≥ c·g(n) instead.
• Θ (tight bound): need BOTH bounds to hold — c₁·g(n) ≤ f(n) ≤ c₂·g(n) for two constants c₁, c₂.

Exam angle: FPSC-style theory questions like this favor simple linear or low-degree polynomial functions — e.g. prove 100n + 5 = O(n), 3n² + 2n = O(n²), or n² + n = O(n²). The exact function changes, but the 4-step template (set up → choose c → solve for n₀ → verify) is always the same — practice it until it's automatic, since graders check the method, not just a guessed final answer. (Not yet seen verbatim in the 2016–2026 papers, but this is a standard theory-of-algorithms proof style well within FPSC's stated syllabus line "Algorithm Analysis and Asymptotic Notations.")

Worked Example: Is log₁₀n an Upper Bound of 5n + 50?

Q: Assume f(n) = 5n + 50 and g(n) = log₁₀n. Is g(n) an upper bound of f(n) — i.e., is f(n) = O(g(n))?

Step 1 — Restate what's being asked: "Is g(n) an upper bound of f(n)" means checking whether f(n) = O(g(n)) — do constants c, n₀ exist such that 5n + 50 ≤ c·log₁₀n for all n ≥ n₀?

Step 2 — Compare growth rates: the standard growth-rate hierarchy is $O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < \cdots$. f(n) is linear; g(n) is logarithmic. A logarithmic function always grows slower than a linear one, no matter how large a constant multiplies it — so f(n) should grow faster, not slower, than g(n).

Step 3 — Prove it formally (limit test): examine the ratio as n → ∞:

$$\lim_{n\to\infty} \frac{f(n)}{g(n)} = \lim_{n\to\infty} \frac{5n+50}{\log_{10} n} = \infty$$

The numerator grows linearly while the denominator grows only logarithmically, so the ratio diverges to infinity instead of settling at 0 or a finite constant.

Step 4 — Interpret the limit:

• limit = 0 → f(n) = O(g(n)) (f grows strictly slower than g)
• limit = finite, nonzero constant → f(n) = Θ(g(n)) (same growth rate)
• limit = ∞ → f(n) is NOT O(g(n)) — f grows strictly faster (in fact f(n) = Ω(g(n)))

Since the limit is ∞, no c and n₀ can exist: for any constant c you try, 5n+50 will eventually overtake c·log₁₀n as n grows, because n outpaces log n by an unbounded margin.

Answer: No. g(n) = log₁₀n is NOT an upper bound of f(n) = 5n+50. It's the reverse: g(n) = O(f(n)) (log n IS upper-bounded by the linear function), and f(n) = Ω(g(n)).

MCQ/Exam Trap: examiners like flipping which function is "asked about" — always re-read whether the question asks "is g(n) an upper bound of f(n)" (checking f=O(g)) vs. "is f(n) an upper bound of g(n)" (checking g=O(f)). Same pair of functions, opposite answer.

Exam angle: when one function is polynomial/linear and the other logarithmic, you rarely need the full c/n₀ algebra — just cite the growth-rate hierarchy ($\log n < n < n\log n < n^2 < 2^n$) plus the limit test as justification. Save the full c, n₀ search for when both functions are the same "family" (e.g. both polynomials), where the ordering isn't obvious by inspection.

Finding the Upper Bound of a Function (general method)

Two distinct skills fall under "find the upper bound": (A) simplifying a messy multi-term function down to its tightest single Big-O class, and (B) deciding, given TWO functions, which one upper-bounds the other. Both build directly on the properties and growth-rate hierarchy above.

(A) Simplifying a multi-term function to its tightest Big-O

Method:

1. Break the function into its individual additive terms.
2. Classify each term's growth order using the hierarchy: $O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$.
3. By the Sum Rule, the tightest upper bound is simply the SINGLE fastest-growing term — drop everything else, including constants.

Worked Example: Find the tightest upper bound of f(n) = 3n² + 20n·log n + 5n + 100.

• 3n² → order n² · 20n·log n → order n log n · 5n → order n · 100 → order 1 (constant)

Comparing against the hierarchy, n² is the fastest-growing of the four. Tightest bound: f(n) = O(n²).

(B) Deciding which of two given functions upper-bounds the other

Method — 3 checks, in order of effort:

1. Hierarchy check (fastest): if both functions are recognizable members of the standard hierarchy, just read off the answer directly — no calculation needed.
2. Limit test (general-purpose): compute $\lim_{n\to\infty} f(n)/g(n)$. If 0, f=O(g); if ∞, g=O(f) instead; if a finite nonzero constant, f=Θ(g).
3. Formal c, n₀ proof (most rigorous, use when asked to "prove"): the 4-step template covered above.

Worked Example: Which is the upper bound: f(n) = n² or g(n) = n·2ⁿ?

Hierarchy check: n² is polynomial; n·2ⁿ is exponential (times a polynomial factor) — exponential always dominates polynomial. Answer: g(n) = n·2ⁿ is the upper bound of f(n) = n², i.e. f(n) = O(g(n)).

Exam angle: part (A) is what you use after building a T(n) from step-counting; part (B) is what direct "is g(n) an upper bound of f(n)" questions (like the log₁₀n example above) are really testing — recognize which one a question wants before you start calculating.

---

Types of Functions in Asymptotic Notation (Growth Categories)

Every function you'll meet in complexity analysis falls into one of five broad growth families. Memorizing this single ordering answers "which grows faster" style MCQs instantly, without doing any limit calculation:

Decr Functions < Const Functions < Log Functions < Poly Functions < Exp Functions

Key reasoning point: the boundary between families never depends on constants or coefficients — only on the SHAPE of the function. 1000·log n is still just a logarithmic function (constants don't change its family), and it is STILL eventually beaten by 0.001·n (a polynomial function), no matter how small that 0.001 coefficient is.

Worked Example: Ordering 9 Mixed Functions

Q: Write the following functions in asymptotically increasing order:

n³, n^3.1, n²log n, log n, (log n)¹⁰, 100, 1 billion, (0.3)ⁿ, (1.5)ⁿ

Step 1 — classify each function by family:

Step 2 — order by family (Decr < Const < Log < Poly < Exp), then break ties within a family:

• Within Constant: 100 < 1 billion (compare the fixed values directly)
• Within Logarithmic: log n < (log n)¹⁰ (a higher power of log n eventually overtakes a lower one)
• Within Polynomial: n²log n < n³ < n^3.1 (n²log n sits just below n³ because of the extra log factor; n^3.1 has the highest degree, so it wins)

Final answer (asymptotically increasing order):

$$(0.3)^n < 100 < 1\text{ billion} < \log n < (\log n)^{10} < n^2\log n < n^3 < n^{3.1} < (1.5)^n$$

Verify the tricky pairs with the limit test:

• n³ vs n²log n: $\lim(n^3 / n^2\log n) = \lim(n/\log n) = \infty$ → n³ grows faster ✓
• n^3.1 vs n³: $\lim(n^{3.1}/n^3) = \lim(n^{0.1}) = \infty$ → n^3.1 grows faster ✓
• (log n)¹⁰ vs n²log n: (log n)¹⁰ is polylogarithmic (no n factor at all), while n²log n has a full n² factor — any positive power of n eventually beats any power of log n, so n²log n wins ✓

Exam angle: this "order these N functions" question is a favorite because it forces you to combine three skills at once: recognizing the 5 growth families, ranking mixed poly-log forms correctly — (log n)^k and n^k·log n are NOT the same thing — and breaking ties within a family. Always classify first, order families, then resolve ties; don't try to eyeball all 9 functions at once.

---

Common Complexity Classes (fastest to slowest)

$$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$

Examples

• O(1): array index access
• O(log n): Binary Search
• O(n): Linear Search
• O(n log n): Merge Sort, Quick Sort (average)
• O(n²): Bubble Sort, Insertion Sort, Selection Sort
• O(2ⁿ): naive recursive Fibonacci

Exam Angle / MCQ Trap

Students often confuse Big-O (worst-case/upper bound) with Big-Theta (tight/average bound) — when a question says an algorithm's complexity "is" X (not "at most" X), it usually means Theta, not O. Know this distinction precisely.

Comparing Decreasing ("Decrement") Functions

So far every example compared functions that GROW as n increases. Some questions instead give functions that DECREASE (decay toward 0) as n grows, and ask you to order them from slowest-to-decrease to fastest-to-decrease. The method mirrors the growth-rate hierarchy: the function whose denominator/"shrinking part" grows fastest is the one that decreases fastest (shrinks to 0 quickest).

Method:

1. Rewrite each function to clearly identify its shrinking part (usually the denominator).
2. Classify each shrinking part using the SAME growth-rate hierarchy: $n < n\log n < n^2 < n^3 < 2^n < 3^n < \cdots$
3. Fastest-growing denominator → fastest decrease (reaches 0 quickest). Slowest-growing denominator → slowest decrease (stays largest longest).
4. When two functions share the same denominator, compare numerators normally — a bigger numerator makes the function bigger at every n (so it decreases more slowly, relatively).

Worked Example: Arrange from slowest to fastest decrease: 100/n, n/2ⁿ, n/n², n²/3ⁿ, n³/3ⁿ

Step 1 — group by denominator's growth order:

• 100/n and n/n² = 1/n → denominator order n (polynomial decay)
• n/2ⁿ → denominator order 2ⁿ (exponential decay, base 2)
• n²/3ⁿ and n³/3ⁿ → denominator order 3ⁿ (exponential decay, base 3 — grows faster than 2ⁿ, so these decrease fastest)

Step 2 — order the groups (n < 2ⁿ < 3ⁿ in growth speed → same order for decrease speed):

n-group decreases slowest, 2ⁿ-group next, 3ⁿ-group decreases fastest.

Step 3 — break ties within each group by comparing numerators:

• Within the n-group: 100/n (numerator 100) is bigger than n/n²=1/n (numerator 1) at every n → 100/n decreases more slowly than n/n².
• Within the 3ⁿ-group: n³/3ⁿ (numerator n³) is bigger than n²/3ⁿ (numerator n²) at every large n → n³/3ⁿ decreases more slowly than n²/3ⁿ.

Final order, slowest to fastest decrease:

$$\frac{100}{n} > \frac{n}{n^2} > \frac{n}{2^n} > \frac{n^3}{3^n} > \frac{n^2}{3^n}$$

Verify numerically at n=50:

The values shrink in exactly that order — confirming $100/n > n/n^2 > n/2^n > n^3/3^n > n^2/3^n$.

Key reasoning point: don't be fooled by which numerator "looks bigger" (n³ > n² > n) — the DENOMINATOR's growth order matters first (n vs 2ⁿ vs 3ⁿ), since exponential decay always beats polynomial decay, and a larger exponential base (3 vs 2) always eventually wins too. Only use the numerator to break ties WITHIN the same denominator family.

Exam angle: this is the same growth-rate hierarchy skill applied to reciprocals/decaying functions instead of growing ones — "arrange slowest to fastest decrease" is a mirror-image phrasing of "arrange slowest to fastest growth," and the hierarchy $n < n\log n < n^2 < 2^n < 3^n$ still does all the work once you've identified each function's dominant shrinking part.

---

📌 Sample & Repeated FPSC Questions (2016–2026)

2025, Paper I, Q11 (MCQ, 1 mark) — Which asymptotic notation gives the strict upper bound for a function?

• A. Omega notation
• B. Big O notation ✅
• C. Theta notation
• D. None of these

MCQ Trap: Don't confuse "upper bound" (O) with "tight bound" (Theta, both bounds) — Omega is specifically the lower bound, the opposite of what this question asks.

2023, Paper I, Q5(a) (8 marks) — For analyzing an algorithm theoretically & asymptotically, give a detailed note on input size, unit of time & order of growth, supported by mathematical equations.

• Input size (n): magnitude of the problem instance (array length, graph vertices/edges, bits in an integer); running time is expressed as T(n) so algorithms can be compared independent of any one instance.
• Unit of time: instead of wall-clock seconds (hardware/compiler-dependent), theoretical analysis counts "basic operations" (comparisons, assignments, arithmetic ops) as a function of n, e.g. T(n) = 3n² + 5n + 2.
• Order of growth: how T(n) scales for large n, keeping only the dominant term and dropping constants/lower-order terms, formalized as:
  • Big-O: $T(n) = O(g(n))$ if $\exists\, c>0, n_0$ such that $T(n) \leq c\cdot g(n)$ for all $n \geq n_0$ (upper bound).
  • Big-Ω: $T(n) = \Omega(g(n))$ — lower bound, analogous inequality reversed.
  • Big-Θ: $T(n) = \Theta(g(n))$ when both O and Ω bounds coincide (tight bound).
• Example: $T(n) = 3n^2 + 5n + 2$ has order of growth $\Theta(n^2)$, since the n² term dominates as n → ∞.

2016, Paper I, Q5(b) (6 marks) — Find the time complexity of Binary Search by resolving the recurrence T(1) = 2 (n ≤ 1), T(n) = 4 + T(n/2) (n > 1), using the iterative substitution method.

$$
\begin{aligned}
T(n) &= 4 + T(n/2) \\
&= 4 + \big[4+T(n/4)\big] = 2(4)+T(n/4) \\
&= 2(4) + \big[4+T(n/8)\big] = 3(4)+T(n/8) \\
&\;\;\vdots \\
&= k(4) + T(n/2^k)
\end{aligned}
$$

Recursion bottoms out when $`n/2^k = 1`$, i.e., $`k = \log_2 n`$. Substituting back:

$$
T(n) = 4\log_2 n + T(1) = 4\log_2 n + 2
$$

→ dropping constants/lower-order terms: $`T(n) = O(\log n)`$.
**Key reasoning point:** confirms Binary Search's O(log n) time — each comparison halves the remaining search space, so the number of halvings until reaching a single element is log₂n.
**2022, Paper I, Q6(c) (4 marks)** — Give the Big-O time complexity of:

int isPrime(unsigned int n) {

for (unsigned int i = 2; (i * i) < n; i++) {

if (n % i == 0) return 0;

}

return 1;

}

**Answer:** $`O(\sqrt n)`$. The loop condition $`i\cdot i < n`$ is equivalent to $`i < \sqrt n`$, so in the worst case (n prime, loop never returns early), the loop runs $`\approx \sqrt n`$ times with O(1) work per iteration.
**Exam angle:** a classic trap — students who don't rewrite `i*i < n` as `i < √n` often misjudge this as O(n). Always convert a squared loop bound into its root form before naming the complexity class.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

MCQs

2025 P-I · Q11. Which asymptotic notation gives the strict upper bound for a function?

• (A) Omega notation
• (B) Big O notation ✅
• (C) Theta notation
• (D) None of these
• Answer: (B) Big O notation (the intended key).
• Why: Big O gives an upper bound, Omega gives a lower bound, and Theta gives a tight (both-sided) bound. Strictly, little-o is the "strict" upper bound, but it is not in the options, so Big O is the answer.

Related past questions

• 2016 Q6(b) break-even point, 2023 Q5(c) order of growth and 2022 Q6(c) O(√n) are on Algorithms Analysis.