Asymptotic Analysis Notes & Formulas

1. Introduction to Asymptotic Analysis

Asymptotic analysis is the fundamental tool for assessing algorithm efficiency by evaluating performance relative to input size growth. In the GATE ecosystem, this is not merely a theoretical exercise-it is a strategic necessity. It allows us to compare algorithms independently of hardware, OS, or compiler optimizations.

Conceptual Grounding:
Asymptotic analysis describes the limiting behavior of a function as $n \to \infty$. We distinguish between:

• Relative Analysis: Hardware/software dependent. It provides exact, system-specific runtimes which are useless for generalized algorithm comparison.
• Absolute Analysis: The industry and exam standard. It abstracts implementation details to provide a mathematical "order of growth" that remains valid on any machine.

The "So What?" Layer (The Specialist's Intuition): GATE questions often present two functions and ask which is "better." In this context, "better" strictly means a lower growth rate. By ignoring machine-specific constants, we shift from "actual running time" to "scalability prediction." Your goal is to identify the dominant term that dictates behavior when $n$ is massive, as this is where performance bottlenecks occur.

2. Fundamental Complexity Terminologies

Precise terminology prevents the ambiguity that examiners exploit in Multiple Select Questions (MSQs).

Key Definitions:

• Input Size ($n$): The primary variable (e.g., number of elements in an array).
• Time Complexity: The rate at which the number of operations increases.
• Space Complexity: Calculated as $\text{Total Space} = \text{Auxiliary Space} + \text{Input Space}$.

Complexity Cases:

• Worst Case ($O$): Upper bound (e.g., Linear Search where $x$ is not present).
• Best Case ($\Omega$): Lower bound (e.g., Linear Search where $x$ is at index 0).
• Average Case ($\Theta$): Expected value over all possible inputs.

The "So What?" Layer (The Space Complexity Trap): A frequent GATE trap involves the distinction between Total Space and Auxiliary Space. For sorting algorithms, we almost always use Auxiliary Space (extra temporary space) to differentiate them. Why? Because every sorting algorithm has a Total Space Complexity of $O(n)$ just to store the input array. Furthermore, never ignore Recursive Stack Space. In a simple recursive add(n), there are $n$ simultaneous stack levels, leading to $O(n)$ space. Contrast this with $n$ calls to a non-recursive pairSum inside a loop, which uses $O(1)$ space because the calls are not simultaneous.

3. The Hierarchy of Growth Functions

Mastering the growth hierarchy is the fastest way to solve complexity-ranking MCQs.

Growth Hierarchy Table (Slowest to Fastest):

| Complexity Class | Notation | Hierarchy Order |
| :--- | :--- | :--- |
| Constant | $1$ | 1 (Slowest) |
| Log-Logarithmic | $\log \log n$ | 2 |
| Logarithmic | $\log n$ | 3 |
| Square Root | $\sqrt{n}$ | 4 |
| Linear | $n$ | 5 |
| Linearithmic | $n \log n$ | 6 |
| Quadratic | $n^2$ | 7 |
| Cubic | $n^3$ | 8 |
| Polynomial | $n^k$ | 9 |
| Quasi-Polynomial | $n^{\log n}$ | 10 |
| Exponential | $c^n$ ($c>1$) | 11 |
| Factorial | $n!$ | 12 |
| Super-Exponential | $n^n$ | 13 (Fastest) |

Advanced Comparisons & Specialist Gotchas:

• The Log-Root-Log Hierarchy: $\log \log n < \sqrt{\log n} < \log n$.
• Factorial Bounds: $2^n < n! < n^n$ (High yield for comparisons).
• The Quasi-Polynomial Correction: A common error is ranking $n^{\log n}$ above $2^n$. To verify, take the log: $\log(n^{\log n}) = (\log n)^2$ vs. $\log(2^n) = n \log 2$. Since linear growth ($n$) beats polylogarithmic growth ($(\log n)^2$), $2^n$ grows faster than $n^{\log n}$.

The "So What?" Layer: Apply the Dominant Term Rule: As $n \to \infty$, lower-order terms (like $5n$ in $60n^2 + 5n + 11$) become mathematically irrelevant. In an MCQ, immediately "pop" lower terms to find the growth rate of the fastest-growing component.

4. Asymptotic Notations: Math and Intuition

Rigorous mathematical definitions are required for GATE Multiple Select Questions (MSQs).

Notation Deep-Dive:

• Big-O ($O$): Upper bound. $f(n) = O(g(n))$ if there exist positive constants $c > 0$ and $n_0 \geq 1$ such that $0 \leq f(n) \leq c \cdot g(n)$ for all $n \geq n_0$.
• Big-Omega ($\Omega$): Lower bound. $f(n) = \Omega(g(n))$ if there exist positive constants $c > 0$ and $n_0 \geq 1$ such that $0 \leq c \cdot g(n) \leq f(n)$ for all $n \geq n_0$.
• Big-Theta ($\Theta$): Tight bound. $f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. This implies $0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n)$ for $c_1, c_2 > 0$ and $n \geq n_0$.
• Little-o ($o$): Non-tight upper bound. $\lim_{n \to \infty } \frac{f(n)}{g(n)} = 0$.
• Little-omega ($\omega$): Non-tight lower bound. $\lim_{n \to \infty } \frac{f(n)}{g(n)} = \infty$.

The "So What?" Layer: A function being $O(n)$ is technically also $O(n^2)$ and $O(2^n)$, as Big-O is just a ceiling. However, GATE usually looks for the tightest upper bound. If the growth rates of $f(n)$ and $g(n)$ are identical, use $\Theta$.

5. Properties of Asymptotic Notations

Use these algebraic properties to simplify complex expressions in seconds.

• Reflexive: $f(n) = O(f(n))$, $f(n) = \Omega(f(n))$, $f(n) = \Theta(f(n))$.
• Symmetric: $f(n) = \Theta(g(n)) \iff g(n) = \Theta(f(n))$ (Does NOT apply to $O$ or $\Omega$).
• Transitive: If $f(n) = O(g(n))$ and $g(n) = O(h(n))$, then $f(n) = O(h(n))$.
• Sum Rule: $f(n) + d(n) = O(\max(g(n), h(n)))$.
• Product Rule: $f(n) \cdot d(n) = O(g(n) \cdot h(n))$.

6. Complexity Analysis of Code Structures

Analysis Strategy:

• Linear Time $O(n)$: Single loops with constant increments (i++).
• Logarithmic $O(\log n)$: Loops where the variable is multiplied or divided (i *= 2).
• Double Logarithmic $O(\log \log n)$: Loops where the variable increases exponentially (i = i^2 or i = \sqrt{i}).
• Nested Loops:
  • Independent: $O(n \cdot m)$.
  • Dependent (Inner loop runs to $i$): $\sum_{i=1}^n i = \frac{n(n+1)}{2} \implies O(n^2)$.

7. Solving Recurrence Relations

• The Master Theorem (GATE Essential): For $T(n) = aT(n/b) + f(n)$ where $a \geq 1, b > 1$:
  • Case 1: If $f(n) = O(n^{\log_b a - \epsilon})$, then $T(n) = \Theta(n^{\log_b a})$.
  • Case 2: If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$.
  • Case 3: If $f(n) = \Omega(n^{\log_b a + \epsilon})$ and regularity holds, then $T(n) = \Theta(f(n))$.
  • The Trap: $f(n)$ must be a polynomial. If $f(n) = n \log n$, standard Master Theorem fails-use the extended version or iteration.
• Advanced Substitution: For $T(n) = T(\sqrt{n}) + c$:
  • Let $n = 2^m$, so $T(2^m) = T(2^{m/2}) + c$.
  • Let $S(m) = T(2^m)$, transforming the relation into $S(m) = S(m/2) + c$.
  • This is logarithmic in $m$: $S(m) = O(\log m)$.
  • Resubstitute $m = \log n \implies \mathbf{O(\log \log n)}$.

8. Complexity Summary: Standard Algorithms

| Algorithm | Best | Average | Worst |
| :--- | :--- | :--- | :--- |
| Bubble/Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ |
| Selection Sort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ |
| Quick Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ |
| Merge/Heap Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ |
| Tree Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ (unbalanced) |

The Quick Sort Insight: Worst-case $O(n^2)$ occurs when the pivot is consistently the smallest or largest element (e.g., on already sorted or reverse-sorted arrays).

9. Space Complexity and Memory Analysis

• In-place Algorithms: Algorithms that require $O(1)$ auxiliary space (e.g., Heap Sort, Insertion Sort).
• Merge Sort: Not in-place; requires $O(n)$ auxiliary space for merging.
• GATE Insight: Always check if the question asks for "Auxiliary Space" or "Space Complexity." All sorting algorithms on $n$ elements have $O(n)$ space complexity because they must store the input.

10. Growth Rate Comparison & MCQ Shortcuts

• L'Hôpital's Rule: If $\lim_{n \to \infty } \frac{f(n)}{g(n)} = \frac{\infty }{\infty }$, differentiate both until the limit is 0 ($g$ grows faster) or $\infty$ ($f$ grows faster).
• Log Shortcut: $a^{\log_b c} = c^{\log_b a}$. Use this to move $n$ to the base.
• Power Beats Log: $n^{0.0001}$ eventually outgrows $(\log n)^{1000}$. Any positive polynomial beats any polylog.

11. Solved GATE PYQ Patterns

• GATE 2011 (Polynomial Ordering): $f_1 = 2^n, f_2 = n^{1.5}, f_3 = n \log n, f_4 = n^{\log n}$.
  • Order: $n \log n < n^{1.5} < n^{\log n} < 2^n$. Correct Option: (A).
• GATE 2020 (AVL insertion): Inserting $n^2$ elements into an AVL tree already containing $n$ elements.
  • The height remains $O(\log (\text{total elements}))$. Total elements $n + n^2 = O(n^2)$.
  • $\text{Height} = O(\log n^2) = O(\log n)$.
  • $n^2$ insertions $\times O(\log n)$ per insertion = $\Theta(n^2 \log n)$.
• GATE 1997 (Concatenation): $O(1)$ concatenation requires circular doubly linked lists to access the tail and head in constant time.

12. Common Exam Traps and Mistakes

• The Master Theorem Trap: Trying to apply it to $T(n) = 2T(n/2) + n \log n$. The $f(n)$ term isn't a polynomial compared to $n^{\log_2 2}$.
• The Constant Power Trap:
  • $2^{n+1} = 2 \cdot 2^n = O(2^n)$ (Correct).
  • $2^{2n} = (2^2)^n = 4^n \neq O(2^n)$ (Incorrect, growth rate changed).
• Sorted vs. Unsorted: Inserting into a sorted linked list is $O(n)$ per element, leading to $O(n^2)$ for $n$ elements.

13. Fast Revision: The GATE Takeaway Sheet

• Hierarchy: $1 < \log \log n < \log n < \sqrt{n} < n < n \log n < n^2 < n^k < n^{\log n} < 2^n < n! < n^n$.
• Recurrence Cheat Sheet:
  • $T(n) = T(n-1) + 1 \to O(n)$
  • $T(n) = T(n-1) + n \to O(n^2)$
  • $T(n) = T(n/2) + 1 \to O(\log n)$
  • $T(n) = 2T(n/2) + n \to O(n \log n)$
• Final Pro-Tip: "Asymptotic" means $n$ is approaching infinity. Never base your answer on small test values (like $n=2$). Evaluate the limiting behavior only.