Growth of functions

ACompressed recap

🧾

O (≤ c·g eventually), Ω (≥), Θ (both); drop constants and lower terms; log bases don't matter, exponential bases do. o/ω strict (limit 0/∞); limit test; compare logs when stuck. Ladder: 1 < log log n < log n < polylog < n^ε < n < n log n < n² < n^(log n) < 2ⁿ < 3ⁿ < n! < nⁿ. Loops: triangle n², inner log i or n/i or log n → n log n, doubling outer loop → n, squaring → log log n, i² ≤ n → √n.

BMerged rule card

1.1.1 Big-O, Big-Ω and Θ: definitions with constants

• O: f ≤ c·g eventually. Ω: f ≥ c·g eventually. Θ: both.
• Drop constant factors and lower-order terms; polynomial degree d → Θ(nᵈ).
• Log bases don't matter; exponential bases and exponent constants do.
• O and Ω need not be tight.

1.1.2 Little-o and little-ω; comparing and ordering functions

• o: f/g → 0; ω: f/g → ∞; constant limit → Θ.
• Compare logs when stuck (but equal logs ≠ equal growth).
• Ladder: 1 < log log n < log n < polylog < n^ε < n < n log n < n² < … < n^(log n) < 2ⁿ < 3ⁿ < n! < nⁿ.
• n^(1/log n) = 2; log n! = Θ(n log n); transitivity, reflexivity, symmetry (Θ), transpose (O/Ω).

1.1.3 Analysing loops: nested, dependent and logarithmic loops

• Inner i → n²/2; inner log i → n log n; inner n/i → n log n; inner log n → n log n.
• Doubling single loop log n; squaring log log n; i² ≤ n → √n.
• Doubling outer loop with inner up to i → Θ(n).
• i < j < k triple loop → C(n, 3) = Θ(n³).

CInterleaved GATE-style questions

Q1MCQ1 markΘ

(n + 5)³ is:

• (A) Θ(n)
• (B) Θ(n⁴)
• (C) Θ(n³)
• (D) Θ(3ⁿ)

Q2MSQ2 marksStatements

Which are true?

• (A) 2^(n/2) = O(2ⁿ)
• (B) 100n = O(n)
• (C) n log n = O(n)
• (D) n² + n = Ω(n²)

Q3MCQ2 marksOrdering

Increasing order of growth: f₁ = 4^(log n), f₂ = n log n, f₃ = n^(1.5), f₄ = 2^(log² n)?

• (A) f₂, f₃, f₁, f₄
• (B) f₂, f₁, f₃, f₄
• (C) f₁, f₂, f₃, f₄
• (D) f₂, f₃, f₄, f₁

Q4MCQ1 markStrictness

Which is true?

• (A) n log n = o(n)
• (B) n² = o(n²)
• (C) n = o(n log n)
• (D) 2ⁿ = o(2ⁿ⁺¹)

Q5NAT2 marksExact count

Exact count of x++ for n = 8?

for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j *= 2)
        x++;

Numerical answer: ________

Q6MCQ1 markLoop growth

Θ of the count?

for (i = 2; i <= n; i = i * i)
    x++;

• (A) Θ(√n)
• (B) Θ(n)
• (C) Θ(log n)
• (D) Θ(log log n)

Q7NAT2 marksExact count

Exact count of x++ for n = 16?

for (i = 1; i < n; i = i * 2)
    for (j = 0; j < i; j++)
        x++;

Numerical answer: ________

Q8MCQ1 markThree loops

Θ of the count?

for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
        for (k = 1; k <= n; k = k * 2)
            x++;

• (A) Θ(n² log n)
• (B) Θ(n²)
• (C) Θ(n³)
• (D) Θ(n log n)

DAnswer Vault