Unit 1: Behaviour Analysis

Opening Hook — The Speed That Separates Good From Great

Learning Outcomes — Bloom's Taxonomy Mapped

Concept Explanation — Behaviour Analysis from Scratch

1. Introduction to Limits and Behaviour of Logic

Why does one algorithm solve a problem in 0.01 seconds while another takes 10 seconds? The answer lies in how the number of operations grows as input size increases. This growth behaviour is what we call algorithmic complexity.

Linear Search — O(n)

C++
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {      // Runs n times in worst case
        if (arr[i] == target) return i;  // 1 comparison per iteration
    }
    return -1;
}

Binary Search — O(log n)

Python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:               # Runs log₂(n) times
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1           # Eliminate left half
        else:
            hi = mid - 1           # Eliminate right half
    return -1

2. Understanding Taxonomy in Worst Case

Every algorithm has three possible behaviours depending on the input:

Why do we focus on worst case? In competitive programming, the judge tests your code against the hardest possible input. If your worst case exceeds the time limit, you get TLE — even if your average case is fast. Worst-case analysis gives you a guarantee.

3. Analysing Effectiveness and Efficiency

An algorithm must be correct (effective) AND fast (efficient). These are independent properties:

A correct but slow algorithm is useless in competitive coding. Bubble Sort correctly sorts an array, but for n = 10⁵, it performs 10¹⁰ operations — that's ~10 seconds on a modern CPU. Merge Sort gives the same correct result in O(n log n) = ~1.7 million operations — under 0.01 seconds.

4. Measuring Time Complexity

Big-O Notation describes the upper bound of an algorithm's growth rate. Formally: f(n) = O(g(n)) if there exist constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀.

The 7 Common Complexity Classes

O(1) — Constant Time

C
int getFirst(int arr[]) {
    return arr[0];  // Always 1 operation regardless of array size
}

O(log n) — Logarithmic Time

C++
// Binary search halves the problem each step
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

O(n) — Linear Time

Python
def find_max(arr):
    mx = arr[0]
    for x in arr:    # Visits each element once
        if x > mx:
            mx = x
    return mx

O(n²) — Quadratic Time

C++
// Bubble Sort — nested loops
for (int i = 0; i < n; i++)
    for (int j = 0; j < n - i - 1; j++)
        if (arr[j] > arr[j+1])
            swap(arr[j], arr[j+1]);

Simplification Rules

Rule 1 — Drop constants: O(2n) = O(n), O(5n²) = O(n²)

Rule 2 — Drop lower-order terms: O(n² + n) = O(n²), O(n³ + n² + n) = O(n³)

Rule 3 — Different variables stay: O(n + m) stays as O(n + m), NOT O(n)

5. Measuring Space Complexity

Space complexity measures the memory an algorithm uses as a function of input size.

Python
# O(n) space — creates a new list
def reverse_copy(arr):
    return arr[::-1]     # New list of size n

# O(1) space — reverses in place
def reverse_inplace(arr):
    i, j = 0, len(arr) - 1
    while i < j:
        arr[i], arr[j] = arr[j], arr[i]
        i += 1; j -= 1

6. Trade-off Concept — Time vs Space

Often you can make an algorithm faster by using more memory, or use less memory at the cost of speed. This is the time-space tradeoff.

Prefix Sum Example — Precompute to Answer Fast

C++
// Without prefix sum: O(n) per query, O(1) space
int rangeSum(int arr[], int l, int r) {
    int sum = 0;
    for (int i = l; i <= r; i++) sum += arr[i];
    return sum;
}

// With prefix sum: O(1) per query, O(n) space
int prefix[N];
void buildPrefix(int arr[], int n) {
    prefix[0] = arr[0];
    for (int i = 1; i < n; i++)
        prefix[i] = prefix[i-1] + arr[i];
}
int querySum(int l, int r) {
    return prefix[r] - (l > 0 ? prefix[l-1] : 0);
}

7. Complexity Analysis of Common Patterns

Pattern 1: Single Loop — O(n)

C++
int sum = 0;
for (int i = 0; i < n; i++) {  // Runs n times
    sum += arr[i];               // O(1) work per iteration
}
// Total: n × O(1) = O(n)

Pattern 2: Nested Loops — O(n²)

Python
for i in range(n):       # n iterations
    for j in range(n):   # n iterations each
        print(i, j)      # O(1) work
# Total: n × n × O(1) = O(n²)

Pattern 3: Binary Search — O(log n)

C++
int lo = 0, hi = n - 1;
while (lo <= hi) {           // Each iteration halves the range
    int mid = (lo + hi) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}
// Range shrinks: n → n/2 → n/4 → ... → 1
// Steps = log₂(n), so O(log n)

Pattern 4: Two Pointer — O(n)

Python
# Find pair with given sum in sorted array
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:            # Each step moves one pointer
        s = arr[left] + arr[right]
        if s == target:
            return (left, right)
        elif s < target:
            left += 1
        else:
            right -= 1
    return None
# Total pointer moves ≤ n, so O(n)

Pattern 5: Sliding Window — O(n)

C++
// Maximum sum subarray of size k
int maxSumWindow(int arr[], int n, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i]; // Initial window
    int maxSum = windowSum;
    for (int i = k; i < n; i++) {
        windowSum += arr[i] - arr[i - k]; // Slide: add right, remove left
        maxSum = max(maxSum, windowSum);
    }
    return maxSum;
}
// Only one pass through the array → O(n)

8. Amortized Analysis (Brief)

9. Competitive Coding Constraints — The Cheat Sheet

The single most valuable skill in competitive coding: reading the constraints and immediately knowing what complexity you need.

Learn by Doing — 3-Tier Lab Structure

C++
for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
        cout << arr[j];

C++
for (int i = 1; i < n; i *= 2)
    cout << i;

C++
for (int i = 0; i < n; i++)
    for (int j = 0; j < 100; j++)
        sum++;

Python
def rec(n):
    if n <= 1: return
    rec(n // 2)
    rec(n // 2)

C++
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
            sum++;

C++
int count = 0;
for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
        if (arr[i] > arr[j]) count++;

Problem Set

Syntax & Tracing (5 Questions)

E1. What is the time complexity of this code? for(int i=0; i<n; i++) for(int j=0; j<m; j++) sum++;

E2. How many times does the inner statement execute? for(int i=1; i<=n; i*=3) print(i);

E3. Given T(n) = T(n/2) + O(1), what is the complexity? Trace for n = 16.

E4. What is the output and complexity of: for i in range(n): for j in range(i): print("*")

E5. Simplify: O(3n² + 5n + 100 + n log n). Show each step.

Programming Problems (8 Questions)

E6. Write a function to find the second largest element in an array in O(n) time and O(1) space.

E7. Implement binary search iteratively in C. Your solution must be O(log n).

E8. Write a sliding window function to find the maximum sum of k consecutive elements. Must be O(n).

E9. Given a sorted array with duplicates, count occurrences of a target value in O(log n).

E10. Implement Two Sum: given an array and target, find two numbers that add up to the target. Do it in O(n) using a hash map.

E11. Write a recursive Fibonacci function. What is its time complexity? Now write an O(n) iterative version.

E12. Given two sorted arrays of size n, find the median of the combined array in O(log n).

E13. Write a function that checks if a string has all unique characters in O(n) time.

Industry Problems (3 Questions)

E14. Zomato has 10 lakh restaurants. Design a search system that finds a restaurant by name in O(1) average time. What data structure would you use?

E15. PhonePe processes 3,800 UPI transactions/second. Each transaction must be checked against a fraud database of 1 million known patterns. What's the minimum complexity needed?

E16. IRCTC handles 25 million Tatkal requests. Design a system that processes bookings with O(log n) search and O(1) insertion into the waiting list.

Interview Questions — Asked at Google/Amazon (3 Questions)

MCQ Assessment Bank — 30 Questions (Bloom's Mapped)

Remember / Identify (Q1–Q5)

Understand / Explain (Q6–Q10)

Apply / Calculate (Q11–Q15)

Analyze / Compare (Q16–Q20)

Evaluate / Judge (Q21–Q25)

Create / Design (Q26–Q30)

Short Answer Questions (8)

SA1. What is Big-O notation? Why do we use it?

Model Answer: Big-O notation describes the upper bound of an algorithm's growth rate as input size approaches infinity. We use it because it's hardware-independent — instead of measuring seconds (which vary by CPU), we measure how operations scale with input size. O(n²) means operations grow quadratically, regardless of the computer.

SA2. Explain with an example why we focus on worst-case analysis.

Model Answer: In competitive coding, the judge tests against the hardest possible inputs. For linear search, best case is O(1) (element at index 0), but worst case is O(n) (element absent). If we plan for average case, our solution might TLE on worst-case test data. Worst case gives a guarantee of maximum execution time.

SA3. Differentiate between auxiliary space and total space complexity.

Model Answer: Auxiliary space is the extra memory beyond the input (e.g., temp variables, auxiliary arrays). Total space = input space + auxiliary space. Example: Merge sort has O(n) total space (n for input + n for auxiliary array) but O(n) auxiliary space. In-place quicksort has O(log n) auxiliary space (recursion stack) and O(n) total space.

SA4. What are the two Big-O simplification rules? Give examples.

Model Answer: Rule 1: Drop constants — O(3n) = O(n), O(100n²) = O(n²). Rule 2: Drop lower-order terms — O(n² + n) = O(n²), O(n³ + n² + n) = O(n³). The dominant term determines growth. For n = 10⁶: n² = 10¹² while n = 10⁶, so the n term is negligible.

SA5. Explain the time-space tradeoff with a real example.

Model Answer: You can often trade memory for speed. Example: Finding if a value exists in an unsorted array — linear scan is O(n) time, O(1) space. Building a HashSet first is O(n) time + O(n) space, but subsequent lookups are O(1). If you have 1 million lookups, HashSet saves 10⁶ × n operations at the cost of O(n) extra memory.

SA6. Why is O(n log n) considered the "sweet spot" for sorting?

Model Answer: It's proven that comparison-based sorting cannot be faster than O(n log n) in the worst case (information-theoretic lower bound). Algorithms like Merge Sort and Heap Sort achieve this bound. It's fast enough for n ≤ 10⁶ (≈20 million operations), making it practical for almost all competitive programming constraints.

SA7. What is amortized analysis? Give an example.

Model Answer: Amortized analysis calculates the average cost per operation over a sequence of operations. Example: Dynamic array (vector) resizing — individual append can cost O(n) during resize, but resize happens only every n insertions. Total cost for n appends ≈ 2n. Amortized cost = 2n/n = O(1) per append.

SA8. How do you read competitive programming constraints to determine required complexity?

Model Answer: Use the rule: ~10⁸ operations/second. For time limit T seconds, max operations = T × 10⁸. Match n to complexity: n ≤ 10⁵ → need O(n log n). n ≤ 5000 → O(n²) works. n ≤ 20 → O(2ⁿ) ok. n ≤ 10 → O(n!) feasible. Always check constraints FIRST before coding.

Long Answer Questions (3)

LA1. Explain all 7 common complexity classes with examples, code, and a growth comparison table. (15 marks)

Model Answer: The seven classes are O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!). O(1) = array indexing — constant regardless of size. O(log n) = binary search — halves problem each step. O(n) = linear scan — visits each element once. O(n log n) = merge sort — divide in log n levels, merge n elements per level. O(n²) = bubble sort — nested loops comparing all pairs. O(2ⁿ) = subset generation — each element is either included or not. O(n!) = permutation generation — n choices for first, n-1 for second, etc. Growth comparison at n=1000: O(1)=1, O(log n)=10, O(n)=1000, O(n log n)=10000, O(n²)=10⁶, O(2ⁿ)=∞, O(n!)=∞. Only O(1) through O(n log n) are practical for large inputs.

LA2. Analyze the complexity of the following 5 algorithmic patterns with code examples: single loop, nested loop, binary search, two pointers, sliding window. (15 marks)

Model Answer: (1) Single loop: iterates n times with O(1) work each → O(n). Example: finding maximum in array. (2) Nested loop: outer runs n, inner runs n → n×n = O(n²). Example: checking all pairs for duplicates. (3) Binary search: halves search space each step → O(log n). Requires sorted data. Example: finding target in sorted array. (4) Two pointers: two indices moving inward, total n moves → O(n). Example: finding pair with target sum in sorted array. (5) Sliding window: window of fixed/variable size moves right, each element enters and leaves once → O(n). Example: maximum sum subarray of size k. Key insight: patterns 4 and 5 convert O(n²) brute force to O(n) by maintaining state incrementally.

LA3. Explain the constraint-to-complexity mapping technique used in competitive programming. How does reading constraints help you choose the right algorithm? Provide a detailed table and 3 problem examples. (15 marks)

Model Answer: Modern computers process ~10⁸ operations/second. For a 1-second time limit, your algorithm must do ≤ 10⁸ operations. Mapping: n≤10→O(n!), n≤20→O(2ⁿ), n≤500→O(n³), n≤5000→O(n²), n≤10⁵→O(n log n), n≤10⁶→O(n), n≤10⁸→O(log n). Example 1: "Sort n numbers, n≤10⁵" → must use O(n log n) sort (merge/quick), not O(n²) bubble sort. Example 2: "Find subset with target sum, n≤20" → O(2²⁰) = ~10⁶, bitmask DP feasible. Example 3: "Given n≤10⁶ numbers, find two with sum = target" → need O(n) solution, use HashMap. This technique is the most valuable competitive programming skill — read constraints first, determine complexity ceiling, then pick algorithm.

Lab Programs

All lab exercises for this unit are integrated into Section D — 3-Tier Labs. The tiered structure provides guided (Tier 1), semi-guided (Tier 2), and open challenge (Tier 3) lab experiences covering Big-O analysis, algorithm optimization, and Codeforces problem solving.

Industry Spotlight — A Day in the Life

Earn With It — Freelance & Income Roadmap

Chapter Summary & Complexity Cheat Sheet

Complexity Cheat Sheet

Checkpoint — Self-Assessment

✅ Unit 1 complete. MCQs: 30. Ready for Unit 2!

[QR: Link to EduArtha video tutorial — Behaviour Analysis & Complexity]