Algorithms Analysis (2016)

Purpose of Algorithm Analysis

• Determines how an algorithm's resource usage (time, space) scales as input size (n) grows — enables comparison independent of hardware/language

Time Complexity Cases

• Best case — minimum time (e.g., already-sorted array for insertion sort → O(n))
• Worst case — maximum time (most commonly reported/tested — guarantees an upper bound)
• Average case — expected time over all possible inputs (hardest to compute rigorously)

Worked Example: Best, Worst, and Average Case — Linear Search

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) return i;   // found
    }
    return -1;                          // not found
}

• Best case: key is at index 0 — loop runs just 1 time → O(1).
• Worst case: key is at the last index, or absent entirely — loop runs all n times → O(n).
• Average case: assuming the key is equally likely at any of the n positions (and always present), expected comparisons = (1+2+…+n)/n = (n+1)/2 → still O(n) (the constant ½ drops out).

Key reasoning point: Big-O is quoted for the worst case unless a question specifically asks otherwise — Linear Search is described as "O(n)", not "O(1)", because O(n) is the guarantee holding for every possible input, not just a lucky one.

Exam angle: when FPSC asks for best/worst/average case complexity, always state a concrete input scenario for each ("best case: element already at index 0") rather than a vague description — examiners award marks for that concrete justification, not just the final O() label.

---

Space Complexity

• Total memory used by the algorithm: input storage + auxiliary/working space + call stack (relevant for recursive algorithms)

Empirical vs Theoretical Analysis

• A priori (theoretical): analyze algorithm mathematically before implementation — hardware-independent, the CSS-tested approach
• A posteriori (empirical): run the actual program and measure real time/memory — hardware-dependent, used for benchmarking

Exam Angle

Always state which case (best/worst/average) you're analyzing when asked for a complexity — examiners frequently deduct marks for giving only one number without specifying the case.

How to Analyze an Algorithm & Build Its Big-O Equation (the complete method)

This is the master method for turning ANY piece of code or pseudocode into a time-complexity equation T(n), then classifying it with Big-O. It connects to two other pages: Asymptotic Notations (step-counting basics + the formal c, n₀ proof) and Recursion (solving recurrence relations for recursive code).

The 4-Stage Process:

1. Identify the input size n — the quantity the algorithm's work scales with (array length, number of nodes, digits in a number, etc.)
2. Identify the "basic operation" — the single dominant operation that determines running time (a comparison in search, a swap/compare in sorting, a multiplication in matrix code). You don't need to count every machine instruction — just track this one operation's count.
3. Set up and solve for T(n) — count how many times the basic operation runs as a function of n, using the code-pattern cookbook below.
4. Classify with Big-O — simplify T(n) by keeping only the dominant/fastest-growing term and dropping constants → name the complexity class.

Code-Pattern Cookbook

Worked Example: Building T(n) End-to-End

void process(int arr[], int n) {
    int total = 0;                       // (1) constant
    for (int i = 0; i < n; i++) {        // (2) loop runs n times
        total += arr[i];                  //     O(1) work inside
    }
    for (int i = 0; i < n; i++) {        // (3) another independent loop, n times
        for (int j = 0; j < n; j++) {    //     nested loop, n times per outer iteration
            cout << arr[i] * arr[j];      //     O(1) work inside
        }
    }
}

Stage 1 — input size: n = size of arr.

Stage 2 — basic operation: treat each +=, comparison, and cout as O(1).

Stage 3 — count:

• Block (1): O(1)
• Block (2): a single loop over n → O(n)
• Block (3): a nested loop, both to n, independent → O(n) × O(n) = O(n²)

Stage 4 — combine and classify:

$$T(n) = O(1) + O(n) + O(n^2)$$

When terms are added, the largest term dominates and swallows the rest, so:

$$T(n) = O(n^2)$$

Key reasoning point: you don't average complexity classes when combining code blocks — you take the MAXIMUM (dominant) one. Loops in sequence still just add their individual counts, but once simplified, only the fastest-growing addend survives in the final O() notation.

Once you have T(n), prove it formally using the c, n₀ method on the Asymptotic Notations page — e.g. for $T(n) = n^2+n+1$, show $n^2+n+1 \leq c\cdot n^2$ for some c (try c=3) and find n₀.

Common Mistakes (FPSC exam traps)

• Confusing "add" vs "multiply": loops in sequence → add their counts. Loops nested inside each other → multiply.
• Ignoring dependent bounds: for j = 0 to i inside for i = 0 to n isn't O(n²) by "obviously nested loops" reasoning alone — sum the series (1+2+...+n) to confirm it (with a hidden factor of ½, which Big-O drops anyway — but show the work).
• Treating a recursive call as free: each recursive call must be counted via a recurrence relation T(n) = ..., not skipped — see the Recursion page for solving these.
• Answering the wrong question: "find the time complexity" wants Big-O; "find T(n)" or "count the number of comparisons" wants the exact equation — read carefully.

Exam angle: reading a code/pseudocode snippet and producing its Big-O appears almost every year on both FPSC CS papers — sometimes standalone, sometimes embedded inside a larger programming question ("...and state its time complexity"). Drilling the cookbook table above until it's automatic is one of the highest-leverage things you can do for this exam.

---

📌 Sample & Repeated FPSC Questions (2016–2026)

2016, Paper I, Q6(b) (6 marks) — For step count expressions $n^2 + 10$ and $2^n/4$, find the breakeven point, i.e., the value of n (starting from 1, 2, …) at which the second expression first becomes greater than the first.

Compare $f(n) = n^2+10$ with $g(n) = 2^n/4$ for increasing n:

• n=1: g=0.5, f=11 → g < f
• n=4: g=4, f=26 → g < f
• n=7: g=32, f=59 → g < f
• n=8: g=64, f=74 → g < f
• n=9: g=128, f=91 → g > f ✅ (breakeven)

Key reasoning points:

• The breakeven point is n = 9 — the first value where the exponential term overtakes the polynomial term.
• This is a concrete instance of a general rule tested repeatedly on CSS papers: exponential growth (2ⁿ) always eventually overtakes polynomial growth (n^k) for any fixed k, no matter how large the polynomial's constants are — only the point at which crossover happens depends on the constants.
• Method to remember: compute both functions at successive integer n until the inequality flips; state the crossover n explicitly rather than just "eventually g wins."

---n## The Four Types of Algorithm AnalysisnBeyond best/worst/average case (already covered above), FPSC sometimes asks for all four standard types of analysis used to evaluate an algorithm's asymptotic behavior:n1. Worst-case analysis — the maximum possible running time over all inputs of size n; the input that causes the most work. This is what Big-O most commonly refers to, since it's the only case that gives a hard guarantee.n2. Best-case analysis — the minimum possible running time; the input causing the least work (e.g., Insertion Sort on an already-sorted array runs in O(n)).n3. Average-case analysis — the expected running time, averaged over all possible inputs of size n under some assumed probability distribution (commonly uniform) — the hardest of the four to compute rigorously, since it requires reasoning about input distributions, not just a single scenario.n4. Amortized analysis — the average cost per operation, taken over a worst-case sequence of many operations on the same data structure — not a single random input, and not a probability distribution. It guarantees that even though any one operation may occasionally be expensive, the total cost across a long sequence stays low, so the per-operation cost averages out.nt- Classic example: a dynamic array's (vector) push_back is O(1) amortized, even though an individual push that triggers a resize-and-copy costs O(n) — because with a doubling growth strategy, such expensive resizes happen rarely enough (only $\\log_2 n$ times over n pushes) that the total cost across n pushes is O(n), i.e., O(1) per push on average.n### Exam Angle / MCQ TrapnDon't confuse average-case (probabilistic — averaging over random inputs to a single operation) with amortized (deterministic worst-case guarantee — averaging the cost of one operation over a long sequence of operations). This distinction is the single most common mix-up examiners test around this topic.n---n## Comparing Order of Growth Between Function PairsnA recurring FPSC question format gives several pairs of functions and asks you to state which has the higher, same, or lower order of growth — resolved by simplifying each function to its dominant term and applying the standard growth hierarchy $O(1) < O(\\log n) < O(n) < O(n\\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$ (see the fuller version of this hierarchy on the Asymptotic Notations page).n## 📌 More Sample & Repeated FPSC Questionsn### 📝 Exam Practice: The Four Types of Analysisn2023, Paper I, Q5(b) (6 marks) — Briefly describe the four types of analysis we may perform to evaluate the asymptotic behavior of an algorithm.nModel answer: see "The Four Types of Algorithm Analysis" section above — Worst-case, Best-case, Average-case, and Amortized analysis, each defined in one to two lines with a concrete example (Insertion Sort for best/worst case, a vector's doubling strategy for amortized).n### 📝 Exam Practice: Order-of-Growth Pairwise Comparisonn2023, Paper I, Q5(c) (6 marks) — Evaluate order of growth of the functions given below. Compare & write down which one has higher, same, or lower order of growth than the other: I. n(n+1) and 2000n² II. 100n² and 0.01n³ III. log₂n and ln n IV. 2^(n-1) and 2^n V. (n-1)! and n!nnPairSimplifyVerdictWhynI. n(n+1) vs 2000n²n²+n vs 2000n²Same order — both Θ(n²)2000 is just a constant multiplier; Big-O/Θ drops constantsnII. 100n² vs 0.01n³order n² vs order n³0.01n³ is higherA cubic term eventually overtakes a quadratic one regardless of how small its constant is — crossover at n=10,000, but the ordering is asymptotic, not about small-n valuesnIII. log₂n vs ln nlog₂n = ln n / ln 2 ≈ 1.4427·ln nSame order — both Θ(log n)They differ only by a constant factor (a base-change), which Θ notation absorbsnIV. 2^(n-1) vs 2^n2^n = 2 · 2^(n-1)Same order — both Θ(2ⁿ)A factor of exactly 2 is still just a constant multiplier, not a growth-rate differencenV. (n-1)! vs n!n! = n · (n-1)!n! is higherThe multiplier here is n itself — not a constant — so the gap between them grows without bound; this is NOT the same situation as pair IVnnKey reasoning point: pairs I, III, and IV all look superficially "different" but collapse to the same order of growth because their difference is only ever a constant factor; pairs II and V genuinely differ in growth class because their ratio (n for the factorial pair, the degree gap for the polynomial pair) grows without bound as n→∞ rather than settling at a fixed constant — that ratio test is the general way to tell these two situations apart.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2016 · Paper-I · Q6(b) · 6 marks

Q. For the step-count expressions n² + 10 and 2ⁿ/4, find the break-even point, that is the first n at which the second expression exceeds the first.

Ans. (The second expression is read as 2ⁿ/4.)

• At n = 8, 64 < 74. At n = 9, 128 > 91, so the break-even point is n = 9. After that the exponential term grows much faster.

2023 · Paper-I · Q5(a) · 8 marks

Q. For analysing an algorithm theoretically and asymptotically, give a detailed note on input size, unit of time and order of growth, supported by mathematical equations.

Ans.

• Input size (n): the quantity that determines the work, such as the number of elements in an array, nodes in a graph, or bits in a number.
• Unit of time: not seconds (which depend on the machine) but the number of basic operations (comparisons, assignments) executed. In the RAM model each basic operation costs one unit, so T(n) is a function of n.
• Order of growth: how T(n) behaves as n becomes large. Constants and lower-order terms are ignored. For T(n) = 3n² + 5n + 2, the n² term dominates, so T(n) = Θ(n²).
• Common orders (slowest to fastest growth): 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!.
• Formal definition: f(n) = O(g(n)) if there are constants c and n₀ with f(n) ≤ c·g(n) for all n ≥ n₀.

2023 · Paper-I · Q5(b) · 6 marks

Q. Briefly describe the four types of analysis we may perform to evaluate the asymptotic behaviour of an algorithm.

Ans.

• Worst-case analysis: the maximum time over all inputs of size n (upper bound, Big O). Example: linear search when the key is absent.
• Best-case analysis: the minimum time (lower bound, Big Omega). Example: the key is the first element.
• Average-case analysis: the expected time over all inputs, assuming a probability distribution.
• Amortized analysis: the average cost per operation over a sequence of operations. Example: dynamic array doubling gives O(1) amortized insertion.

2023 · Paper-I · Q5(c) · 6 marks

Q. Compare the order of growth of: I. n(n+1) and 2000n² II. 100n² and 0.01n³ III. log²n and ln n IV. 2ⁿ⁻¹ and 2ⁿ V. (n−1)! and n!

Ans.

2022 · Paper-I · Q6(c) · 4 marks

Q. Write the time complexity (Big-O) of the isPrime function whose loop runs for (i = 2; i*i < n; i++).

Ans.

• The loop continues while i² < n, that is i < √n, so it runs at most about √n times, each iteration doing one modulus.
• Time complexity: O(√n), with O(1) extra space.

2026 · Paper-I · Q5(b) · 6 marks

Q. What is the difference between time complexity and space complexity? Explain with examples.

Ans.

• Time complexity: how the running time (number of operations) grows with input size n.
• Space complexity: how the extra memory needed grows with n.

• Trade-off: a hash table spends extra memory to cut search time to O(1), while in-place algorithms save memory but may take longer.

MCQs

2026 P-I · Q11. You are analysing an algorithm's efficiency. What do you consider?

• (A) Code length
• (B) Time and space complexity ✅
• (C) Programmer's experience
• (D) None of these
• Answer: (B) Time and space complexity.
• Why: efficiency is measured by how the running time and the memory use grow with the input size. Code length and the programmer's experience do not measure how well the algorithm itself performs.