Asymptotic Analysis

# CHAPTER 4

Asymptotic Analysis #

1. Introduction #

2. Learning Objectives #

• Execute line-by-line complexity analysis on source code.

• Apply the "Drop the Constants" rule.

• Apply the "Drop the Non-Dominant Terms" rule.

• Differentiate between Addition (Sequential logic) and Multiplication (Nested logic).

3. Rule 1: Drop the Constants #

Example Code:

def print_twice(arr):
    # Loop 1: Takes N steps
    for item in arr:
        print(item)
        
    # Loop 2: Takes N steps
    for item in arr:
        print(item)

• Total Steps: N + N = 2N.

• Asymptotic Reduction: O(2N) -> O(N).

• The final Time Complexity is strictly $O(N)$.

*Rule: $O(500)$, $O(10)$, and $O(1)$ all mathematically reduce to $O(1)$ Constant Time.*

4. Rule 2: Drop the Non-Dominant Terms #

Example Code:

public void complexFunction(int[] arr) {
    int n = arr.length;
    
    // Part 1: Nested Loops (N * N steps)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println("Pair");
        }
    }
    
    // Part 2: Single Loop (N steps)
    for (int k = 0; k < n; k++) {
        System.out.println("Single");
    }
}

• Total Steps: N² + N.

• As N approaches infinity (e.g., 1 Million), N² equals 1 Trillion. N equals 1 Million. The 1 Million is less than 0.0001% of the total workload. It is mathematically irrelevant.

• Asymptotic Reduction: O(N² + N) -> O(N²).

• We aggressively delete all smaller mathematical terms and only keep the absolute highest growth curve.

5. Rule 3: Addition vs. Multiplication #

#### Sequential = Add If logic happens sequentially (one after another), you ADD.

for (int i = 0; i < A; i++) { ... } // Takes A steps
for (int j = 0; j < B; j++) { ... } // Takes B steps

• Total: O(A + B). *(Note: If A and B are two entirely different arrays, you CANNOT reduce this to O(N). You must keep both variables!)*

#### Nested = Multiply If logic happens *inside* other logic, you MULTIPLY.

for (int i = 0; i < A; i++) {       // Runs A times
    for (int j = 0; j < B; j++) {   // Runs B times FOR EVERY A
        // ...
    }
}

• Total: O(A * B).

6. Analyzing Real-World Code (Step-by-Step) #

function findMatch(arrA, arrB) {
    let count = 0;                      // O(1)

    for (let i = 0; i < arrA.length; i++) {      // O(A)
        for (let j = 0; j < arrB.length; j++) {  // O(B)
            if (arrA[i] === arrB[j]) {           // O(1)
                count++;                         // O(1)
            }
        }
    }
    
    for (let k = 0; k < 100000; k++) {  // O(100000) -> Reduces to O(1)
        console.log("Processing...");
    }

    return count;                       // O(1)
}

The Math:

1. 1. The nested loops run A * B times. Inside, they do $O(1)$ logic. Total: $O(A * B)$.

1. 2. The massive third loop runs 100,000 times, but it is a hardcoded constant. It does NOT scale with the input arrays. Therefore, it is $O(1)$.

1. 3. Equation: $O(A * B) + O(1) + O(1)$.

1. 4. Drop non-dominant terms.

1. 5. Final Big O: $O(A * B)$.

7. Analyzing Logarithmic Code O(log N) #

# Look at the step: i = i * 2!
def logarithmic_function(n):
    i = 1
    while i < n:
        print(i)
        i = i * 2 # The iterator jumps exponentially!

If n = 100, the loop runs for 1, 2, 4, 8, 16, 32, 64. It finishes in 7 steps! Because the iterator covers the distance exponentially, the Time Complexity collapses logarithmically to $O(\log N)$.

8. Real-World Applications #

1. 1. Code Reviews: Senior engineers actively perform Asymptotic Analysis mentally during GitHub PR reviews. If they spot a hidden O(N²) nested loop inside a microservice, they reject the code immediately.

1. 2. Library Functions: You must analyze hidden complexities. In Python, if item in list: is secretly an $O(N)$ loop! If you place that inside a for loop, you have unknowingly written an $O(N²)$ catastrophe!

9. Common Mistakes #

• Assuming all nested loops are $O(N²)$: If you have an outer loop 0 to N, and an inner loop 0 to 5, the inner loop is a constant! The total complexity is N * 5, which reduces to $O(N)$ Linear Time! Always analyze the boundaries of the loops carefully.

10. Exercises #

1. 1. Determine the Big O for: O(N³ + N² + N + 1000).

1. 2. Analyze the following code:

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // ...
    }
}

*(Hint: The inner loop starts at i, not 0. It runs N, N-1, N-2... times. Use the mathematical sum of an arithmetic sequence to find the Big O!).*

11. MCQs with Answers #

12. Interview Preparation #

• *Algorithmic Analysis:* "Analyze this code: for (i=0; i<n; i++) { for (j=i; j<n; j++) { ... } }." *(Answer: This is still O(N²)! The inner loop runs N times, then N-1, then N-2. The sum is (N * (N+1)) / 2. Drop the constants and the /2. The dominant term is strictly N²!).*

13. FAQs #

14. Summary #

15. Next Chapter Recommendation #