Asymptotic notation, recurrences and analysis techniques notes — Unit 1

An algorithm is a finite sequence of unambiguous instructions to solve a specific problem. However, there are often dozens of different algorithms that solve the exact same problem (e.g., sorting an array). How do we mathematically prove which one is 'better'?

⇒1.1 The Problem with Physical Time

We cannot simply run two algorithms and measure their execution time in seconds using a stopwatch. Execution time in seconds is highly dependent on hardware.

• A terrible sorting algorithm (Bubble Sort) running on a modern 5GHz supercomputer might finish in 0.1 seconds.
• A brilliant sorting algorithm (Merge Sort) running on a 1990s Pentium processor might take 5.0 seconds.

If we only looked at physical time, we would incorrectly conclude Bubble Sort is better. Therefore, algorithm analysis must be hardware-independent.

⇒1.2 The RAM Model of Computation

To mathematically analyze an algorithm, we assume a generic, hypothetical computer called the Random Access Machine (RAM).

• Instructions are executed sequentially, one at a time.
• Every basic operation (addition, assignment, boolean comparison) takes exactly 1 constant unit of time ($c$).
• Memory access takes exactly 1 constant unit of time.
• Memory is infinite.

Instead of measuring seconds, we measure the number of basic operations the algorithm performs as a function of the input size, $n$. This is the absolute core of DAA.

⇒2.1 Time Complexity

Let $T(n)$ be the total time taken by an algorithm for an input of size $n$.

Consider a simple loop that finds the maximum element in an array of size $n$.
1. Initialize `max = array[0]` (Takes $c_1$ time).
2. Loop from $i = 1$ to $n-1$.
3. Inside the loop, compare `array[i] > max` and assign if true. (Takes $c_2$ time per iteration).

The total time function is exactly $T(n) = c_1 + c_2(n-1)$. Notice that as $n$ approaches infinity (a billion elements), the constants $c_1$ and $c_2$ become completely mathematically irrelevant. The only thing that dictates the growth rate is $n$. Thus, we say the time complexity is proportional to $n$.

⇒2.2 Space Complexity

Let $S(n)$ be the total extra memory space required by the algorithm as a function of $n$.

This does not include the memory required to hold the input itself. It only includes auxiliary space (temporary variables, stack frames for recursion). An algorithm that sorts an array "in-place" without creating a new array has a constant space complexity, denoted as $O(1)$.

For many algorithms, the execution time $T(n)$ depends not just on the size of the input, but on the nature of the input. A sorting algorithm might finish instantly if the array is already sorted, but take hours if the array is in reverse order.

⇒3.1 Worst-Case Analysis (The Standard)

The maximum possible time the algorithm will take for any input of size $n$. We assume the universe hates us and gives us the most difficult, pathological input possible.

This is the most critical metric in computer science. It guarantees that the algorithm will NEVER take longer than this bound. Mission-critical systems (like airplane avionics) strictly require worst-case guarantees.

⇒3.2 Best-Case Analysis

The minimum possible time for an input of size $n$. The input is perfectly ideal. This is generally useless in practice because we cannot rely on the user providing perfect data.

⇒3.3 Average-Case Analysis

The expected time averaged over all possible inputs of size $n$. This requires complex probability theory. We must define the statistical distribution of the inputs (e.g., assume all permutations are equally likely), multiply the time taken for each permutation by its probability, and sum them. Often, the average case is mathematically identical to the worst case.

Asymptotic notation is a mathematical language used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity. It allows us to discard lower-order terms and constants.

⇒4.1 Formal Mathematical Definition of Big-O

Big-O notation provides an Asymptotic Upper Bound. It represents the Worst-Case scenario.

Let $f(n)$ and $g(n)$ be functions mapping non-negative integers to real numbers.
We say that $f(n) = O(g(n))$ if and only if there exist positive constants $c$ and $n_0$ such that:

$0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$

⇒4.2 Intuition and Example

In plain English: No matter how wild $f(n)$ gets, once the input size $n$ passes a certain threshold ($n_0$), $f(n)$ will never, ever grow faster than a constant multiple of $g(n)$. The curve of $c \cdot g(n)$ will always remain physically above the curve of $f(n)$ on a graph.

Example Proof: Prove that $f(n) = 3n^2 + 5n + 2$ is $O(n^2)$.
We must find $c$ and $n_0$ such that $3n^2 + 5n + 2 \le c cdot n^2$.
For $n \ge 1$, we know that $n \le n^2$ and $1 \le n^2$.
Therefore: $3n^2 + 5n + 2 \le 3n^2 + 5n^2 + 2n^2 = 10n^2$.
Thus, we choose $c = 10$ and $n_0 = 1$. The condition holds. $f(n) = O(n^2)$.

⇒5.1 Big-Omega ($\Omega$) - The Lower Bound

Big-Omega provides an Asymptotic Lower Bound. It represents the Best-Case scenario. It guarantees an algorithm will take at least this much time.

Formal Definition: $f(n) = \Omega(g(n))$ if there exist positive constants $c$ and $n_0$ such that:
$0 \le c \cdot g(n) \le f(n)$ for all $n \ge n_0$

The curve of $c \cdot g(n)$ will always remain physically below the curve of $f(n)$.
Example: An algorithm that prints an array of size $n$ takes $\Omega(n)$ time, because you physically cannot print $n$ items in less than $n$ steps, no matter how lucky you are.

⇒5.2 Big-Theta ($\Theta$) - The Tight Bound

Big-Theta provides an Asymptotic Tight Bound. It means the algorithm grows exactly at this rate, no faster and no slower. It is the most precise notation.

Formal Definition: $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ AND $f(n) = \Omega(g(n))$.

There exist constants $c_1, c_2,$ and $n_0$ such that:
$c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ for all $n \ge n_0$

The function $f(n)$ is mathematically 'sandwiched' between $c_1g(n)$ and $c_2g(n)$.

While Big-O and Big-Omega allow for the bound to be tight (inclusive of equality), the "little" notations denote strict, non-inclusive bounds.

⇒6.1 little-o notation ($o$)

Provides an upper bound that is strictly NOT tight. The function $f(n)$ becomes insignificant relative to $g(n)$ as $n$ approaches infinity.

Formal Limit Definition: $f(n) = o(g(n))$ if $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$.

Example: $2n = o(n^2)$, but $2n^2 \neq o(n^2)$. The function $2n^2$ is bounded by $n^2$ (Big-O), but it grows at the exact same quadratic rate, so it is not strictly dominated (little-o).

⇒6.2 little-omega notation ($\omega$)

Provides a lower bound that is strictly NOT tight. The function $f(n)$ dominates $g(n)$ as $n$ approaches infinity.

Formal Limit Definition: $f(n) = \omega(g(n))$ if $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$.

Example: $n^3 = \omega(n^2)$. The cubic function strictly outgrows the quadratic function.

As an engineer, you must instantly recognize which mathematical functions are inherently faster than others. This hierarchy is the foundation of algorithm optimization.

⇒7.1 The Hierarchy of Complexities

From fastest (best) to slowest (worst):

• $O(1)$ - Constant: Execution time is entirely independent of input size. (e.g., Array index lookup).
• $O(\log n)$ - Logarithmic: Extremely fast. The input is halved at every step. Even for 1 billion items, it takes only ~30 steps. (e.g., Binary Search).
• $O(n)$ - Linear: Time grows directly proportionally to input size. (e.g., Searching an unsorted list).
• $O(n \log n)$ - Linearithmic: The absolute mathematical limit for comparison-based sorting algorithms. (e.g., Merge Sort, Quick Sort).
• $O(n^2)$ - Quadratic: Double nested loops. Acceptable for small datasets (n < 10,000), but paralyzing for large ones. (e.g., Bubble Sort, Matrix addition).
• $O(n^3)$ - Cubic: Triple nested loops. Very slow. (e.g., Matrix Multiplication).
• $O(2^n)$ - Exponential: Unusable in real-world scenarios for $n > 50$. Time doubles with every single new element. (e.g., Naive recursive Fibonacci, checking all subsets).
• $O(n!)$ - Factorial: The absolute worst. Time required to check all permutations of a set. (e.g., The Traveling Salesperson Problem).

When an algorithm calls itself recursively (like Merge Sort or Binary Search), its time complexity cannot be expressed as a simple algebraic equation like $T(n) = 3n + 5$.

Instead, the execution time is defined in terms of its own execution time on smaller inputs. This creates a Recurrence Relation.

⇒8.1 Anatomy of a Recurrence

Consider Merge Sort. It takes an array of size $n$, splits it into two halves of size $n/2$, recursively sorts both halves, and then merges them in linear time $O(n)$.

The mathematical recurrence equation is:

$T(n) = \begin{cases} \Theta(1) & \text{if } n = 1 \\ 2T(n/2) + \Theta(n) & \text{if } n > 1 \end{cases}$

To find the Big-O time complexity, we must "solve" this equation to remove the $T$ from the right side. We have three mathematical techniques to do this: Substitution, Recursion Tree, and the Master Theorem.

Also known as mathematical induction. This method involves guessing the bound and then using mathematical induction to prove our guess is correct.

⇒9.1 The Process

Solve $T(n) = 2T(\lfloor n/2 \rfloor) + n$.

Step 1: Guess. We guess that the solution is $O(n \log n)$.
Step 2: Formulate the proof. We must prove that $T(n) \le c \cdot n \log n$ for an appropriate choice of constant $c>0$.
Step 3: Inductive Step. Assume the bound holds for all positive $m < n$. In particular, it holds for $m = \lfloor n/2 \rfloor$.
Substitute the assumption into the recurrence:
$T(n) \le 2(c \cdot \lfloor n/2 \rfloor \log \lfloor n/2 \rfloor) + n$
$T(n) \le cn \log(n/2) + n$
$T(n) = cn \log n - cn \log 2 + n$
Since $\log_2 2 = 1$:
$T(n) = cn \log n - cn + n$
$T(n) \le cn \log n$ (This is true as long as $c \ge 1$).

Conclusion: The induction holds. Our guess was absolutely correct. $T(n) = O(n \log n)$.

Flaw: The substitution method is mathematically rigorous, but it requires you to magically guess the correct answer before you start. If you guess wrong, the math falls apart.

The Recursion Tree method provides a visual way to generate a good guess, which can then be proved via substitution. It models the cost (time) of execution at each level of the recursive call stack.

⇒10.1 Constructing the Tree

Solve $T(n) = 3T(n/4) + cn^2$. (Algorithm splits input into 4 pieces, calls itself 3 times, and takes quadratic time to combine the results).

• Level 0 (Root): The cost is $cn^2$. It produces 3 children, each with size $n/4$.
• Level 1: There are 3 nodes. Each node has a cost of $c(n/4)^2 = cn^2 / 16$. The total cost of this level is $3 \times (cn^2 / 16) = \frac{3}{16} cn^2$.
• Level 2: There are 9 nodes. Each node has size $n/16$. Total cost is $9 \times c(n/16)^2 = (\frac{3}{16})^2 cn^2$.

We can see a pattern forming. The cost at level $i$ is $(\frac{3}{16})^i cn^2$.

⇒10.2 Summing the Costs

The total cost of the algorithm is the sum of the costs of all levels in the tree. Because the common ratio $(3/16)$ is strictly less than 1, this forms a decreasing geometric series.

In a decreasing geometric series, the sum is dominated by the very first term (the root). Therefore, the total time is bound by the root cost. $T(n) = O(n^2)$.

The Master Method is a powerful mathematical formula that provides a direct, instant solution to recurrences without requiring tree drawing or induction proofs. However, it only applies to recurrences of a specific mathematical form.

⇒11.1 The Standard Form

The recurrence must be in the exact form:
$T(n) = aT(n/b) + f(n)$
Where:
- $a \ge 1$ (Number of recursive calls).
- $b > 1$ (Factor by which the input is divided).
- $f(n)$ is asymptotically positive (The cost of dividing and merging).

To use the theorem, we must calculate a critical value called the Watershed Function: $n^{\log_b a}$. We then compare this watershed value to the combination cost $f(n)$.

There are three distinct mathematical cases based on this comparison.

⇒12.1 Case 1: The Leaves Dominate

If $f(n) = O(n^{\log_b a - \epsilon})$ for some constant $\epsilon > 0$.

In English: The watershed function $n^{\log_b a}$ grows polynomially faster than $f(n)$. This means the vast majority of the execution time is spent down at the base cases (the leaves of the recursion tree).

Solution: The time complexity is exactly the watershed function: $T(n) = \Theta(n^{\log_b a})$.

Example: $T(n) = 9T(n/3) + n$.
$a=9, b=3, f(n)=n$.
Watershed: $n^{\log_3 9} = n^2$.
Compare: $n$ versus $n^2$. $n^2$ is polynomially larger. Therefore, Case 1 applies. $T(n) = \Theta(n^2)$.

⇒12.2 Case 2: Equilibrium

If $f(n) = \Theta(n^{\log_b a})$.

In English: The watershed function and $f(n)$ grow at the exact same rate. The cost is distributed evenly across all levels of the tree.

Solution: Multiply the watershed by a logarithmic factor: $T(n) = \Theta(n^{\log_b a} \log n)$.

Example (Merge Sort): $T(n) = 2T(n/2) + n$.
$a=2, b=2, f(n)=n$.
Watershed: $n^{\log_2 2} = n^1 = n$.
Compare: $n$ versus $n$. They are identical. Case 2 applies. $T(n) = \Theta(n \log n)$.

⇒13.1 Case 3: The Root Dominates

If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some constant $\epsilon > 0$.

In English: The combination cost $f(n)$ grows polynomially faster than the watershed function. This means the vast majority of the execution time is spent at the very top of the tree, merging the results together.

*(Requirement: Case 3 also requires a regularity condition to hold: $a \cdot f(n/b) \le c \cdot f(n)$ for some constant $c < 1$).*

Solution: The time complexity is simply the combination cost itself: $T(n) = \Theta(f(n))$.

Example: $T(n) = 3T(n/4) + n \log n$.
$a=3, b=4, f(n)=n \log n$.
Watershed: $n^{\log_4 3} \approx n^{0.793}$.
Compare: $n \log n$ versus $n^{0.793}$. The function $f(n)$ is polynomially larger. Case 3 applies. $T(n) = \Theta(n \log n)$.

The Master Theorem is not a magic bullet. It mathematically fails under several specific conditions.

⇒14.1 When it Fails

• Non-Polynomial Differences: The theorem requires the difference between $f(n)$ and the watershed to be polynomial (the $\epsilon$ factor).
  Example: $T(n) = 2T(n/2) + n \log n$.
  Watershed is $n$. $f(n)$ is $n \log n$. The ratio is $\log n$. Because $\log n$ is asymptotically smaller than $n^{\epsilon}$ for any $\epsilon > 0$, the difference is not polynomial. The Master Theorem completely fails here. You must use the Recursion Tree method.
• Variable Values of 'a': The number of recursive calls must be a constant. If $a$ is a function of $n$ (e.g., $T(n) = nT(n/2) + n$), the theorem fails.
• Non-Constant Division: If the input is not divided by a constant fraction (e.g., $T(n) = T(n-1) + 1$, where the input is subtracted, not divided), the theorem fails.

Unit 1 is the most mathematically rigorous unit in the entire B.Tech curriculum. You must be comfortable with limits, logarithms, and geometric series.

⇒15.1 University Exam Checklist

• Write the formal mathematical definitions for Big-O ($O$), Big-Omega ($\Omega$), and Big-Theta ($\Theta$).
• Prove mathematically that $5n^2 + 2n + 1 = O(n^2)$ by finding constants $c$ and $n_0$.
• Explain the difference between Time Complexity and Space Complexity.
• Why is Worst-Case analysis preferred over Best-Case analysis in engineering?
• Solve the recurrence $T(n) = 2T(n/2) + n$ using the Substitution Method. Show the induction proof.
• Draw a Recursion Tree to solve $T(n) = 3T(n/4) + cn^2$. Show the cost at each level and the final geometric series.
• State the three cases of the Master Theorem.
• Solve $T(n) = 8T(n/2) + n^2$ using the Master Theorem. Explicitly state which case applies and why.
• Explain two scenarios where the Master Theorem cannot be used to solve a recurrence.