Unit 1: Behaviour Analysis

I. Foundations of Algorithmic Behaviour

Algorithmic behaviour analysis studies how an algorithm responds to changing input sizes and whether it remains correct, feasible, and resource-efficient under stated constraints. In competitive coding, this analysis connects program logic with mathematical growth: a logically correct solution is useful only if it finishes within the available time and memory.

• Input size: Represented by (n), it may denote the number of array elements, vertices, characters, queries, or another dominant quantity.
• Basic operation: A comparison, assignment, arithmetic operation, or data-structure access used as a unit for estimating work.
• Resource model: Running time and auxiliary memory are measured as functions of input size rather than as fixed machine-dependent values.
• Asymptotic viewpoint: Constant factors and lower-order terms are usually ignored when comparing growth for large (n).
• Correctness assumption: Complexity analysis does not prove that an algorithm produces the right answer; correctness and efficiency must be established separately.
• Machine model: Standard analysis commonly assumes a Random Access Machine in which ordinary fixed-width arithmetic and memory access take constant time.
• Constraint-driven selection: Input limits determine which complexity classes are practical under the contest’s time and memory limits.

II. Limits and Logical Behaviour — Connecting Constraints, Correctness, and Growth

A. Introduction to limits and behaviour of logic

Limits define the valid input domain and available resources, while logical behaviour describes the sequence of decisions and state changes made by an algorithm.

• Constraint interpretation: A declaration such as (1 \le n \le 2 \times 10^5) gives both correctness obligations and performance information.
  • The lower limit requires handling the smallest valid case.
  • The upper limit helps reject algorithms such as (O(n^2)), which would perform roughly (4 \times 10^{10}) pair operations.
• Control-flow behaviour: Loops, branches, recursion, and early termination determine which operations execute for a particular input.
  • A loop from (0) to (n-1) executes (n) times.
  • Nested independent loops of length (n) execute (n^2) iterations.
  • Repeatedly halving a value produces approximately (\log_2 n) iterations.
• Boundary behaviour: Errors often arise at (n=0), (n=1), the maximum (n), duplicate values, sorted data, or values near numeric limits.
• Logical invariants: An invariant is a condition that remains true throughout an algorithm. In binary search, if the target exists, it must remain inside the current interval ([low, high]).
• Termination: Every loop or recursive call must progress toward a stopping condition. Binary search terminates because the interval length strictly decreases.
• Numeric limits: Fixed-width data types restrict representable values. A signed 32-bit integer has maximum value (2^{31}-1); therefore, products such as (10^9 \times 10^9) require a wider type.
• Mathematical limiting behaviour: Asymptotic growth can be formalized using a ratio:

lim(n -> infinity) f(n) / g(n)

• If the limit is a positive finite constant, (f) and (g) have the same asymptotic order.
• For (f(n)=3n^2+5n+2) and (g(n)=n^2), the limit is (3), so (f(n)=\Theta(n^2)).

B. Applications and Limitations

Behaviour analysis predicts scalability, but it remains an abstraction of actual execution.

• Feasibility screening: Approximate operation counts quickly eliminate unsuitable approaches before implementation.
• Edge-case design: Constraints identify cases that must be represented in tests and correctness arguments.
• Model limitation: Cache effects, compiler optimization, language overhead, and input/output speed can make two algorithms with the same asymptotic order perform differently.
• Domain limitation: Complexity statements apply only under their assumptions; hash-table lookup is expected (O(1)), but may be (O(n)) in an adversarial worst case.

III. Worst-Case Taxonomy — Classifying Upper Bounds

A. Understanding taxonomy in worst case

Worst-case analysis gives the maximum resource usage over all valid inputs of size (n), providing a dependable upper-bound guarantee.

• Worst-case function: If (T(x)) is the cost for input (x), then

W(n) = max { T(x) : |x| = n }

• (W(n)) is the worst-case cost.
• (|x|=n) means that input (x) has size (n).
  • Big-O notation: (f(n)=O(g(n))) when constants (c>0) and (n_0) exist such that

0 <= f(n) <= c*g(n) for every n >= n0

It expresses an asymptotic upper bound. For example, (3n+7=O(n)).

• Big-Omega notation: (f(n)=\Omega(g(n))) gives an asymptotic lower bound.
• Big-Theta notation: (f(n)=\Theta(g(n))) when it is both (O(g(n))) and (\Omega(g(n))), giving a tight asymptotic bound.
• Common worst-case classes:
  • (O(1)): array indexing or stack-top access.
  • (O(\log n)): binary search in a sorted array.
  • (O(n)): scanning all elements to find a maximum.
  • (O(n\log n)): merge sort and comparison-based efficient sorting.
  • (O(n^2)): examining every pair in an array.
  • (O(2^n)): enumerating all subsets.
  • (O(n!)): enumerating all permutations.
• Case distinction: Best, average, and worst cases describe different inputs of the same size.
  1. Best case: Linear search finds the target first, requiring one comparison.
  2. Worst case: The target is last or absent, requiring (n) comparisons.
• Amortized distinction: Amortized analysis bounds the average cost across a sequence of operations, not across random inputs. Dynamic-array insertion is amortized (O(1)), although an individual resize costs (O(n)).
• Guarantee value: Worst-case bounds are especially important when tests may deliberately contain inputs that trigger maximum work.

IV. Algorithm Quality — Correct Results and Practical Performance

A. Analysing the effectiveness and efficiency of algorithms

Effectiveness concerns whether an algorithm solves the required problem correctly, while efficiency concerns how economically it uses computational resources.

1. Effectiveness:

   • Specification compliance: The output must satisfy the problem statement for every valid input.
   • Correctness: A proof may use loop invariants, induction, contradiction, or an exchange argument.
   • Completeness: All required cases must be handled, including empty ranges, duplicates, disconnected graphs, and unreachable states.
   • Termination: The algorithm must finish after a finite number of steps.
   • Robustness: Arithmetic overflow, recursion depth, invalid indexing, and ambiguous sentinel values must be prevented.

2. Efficiency:

   • Time use: Count how the dominant operations grow with input size.
   • Space use: Include auxiliary arrays, recursion stacks, tables, and data-structure overhead.
   • Scalability: Compare the predicted workload with the maximum constraints.
   • Implementation cost: A theoretically faster method may be inappropriate if it is complex, error-prone, or has large constants for small inputs.

• Worked comparison: To detect whether a sorted array contains a target, linear search is correct in (O(n)), while binary search is correct in (O(\log n)). For (n=1{,}000{,}000), binary search needs at most about (\lceil\log_2 1{,}000{,}000\rceil=20) interval reductions, whereas linear search may need one million comparisons.
• Empirical measurement: Benchmarks can compare real implementations, but inputs must represent expected and adversarial patterns.
• Combined judgment: An incorrect (O(n)) solution is ineffective, while a correct (O(2^n)) solution may be computationally infeasible for large (n).

V. Complexity Measurement — Quantifying Time and Memory Growth

A. Measuring time and space complexity of algorithm

Complexity measurement derives resource-growth functions from the algorithm’s operations and retained storage.

• Sequential statements: Add their costs and retain the dominant term.

T(n) = O(n) + O(n log n) + O(1) = O(n log n)

• Simple loops: A loop with (n) constant-time iterations has (T(n)=cn+d=\Theta(n)).
• Nested loops: Multiply iteration counts when loops are dependent through repeated execution. Two full loops of size (n) give (\Theta(n^2)).
• Non-rectangular loops: The code below performs (1+2+\cdots+n) operations:

for i = 1 to n:
    for j = 1 to i:
        process(i, j)

1 + 2 + ... + n = n(n + 1)/2 = Theta(n^2)

• Logarithmic loops: If a variable doubles each iteration, the number of iterations is the smallest (k) satisfying (2^k \ge n), namely (\lceil\log_2 n\rceil).
• Conditional branches: Worst-case time uses the more expensive reachable branch, together with the cost of evaluating the condition.
• Recursion: Express repeated work through a recurrence. Merge sort follows

T(n) = 2T(n/2) + Theta(n) = Theta(n log n)

Here, (T(n)) is running time for (n) elements, (2T(n/2)) represents two recursive halves, and (\Theta(n)) represents merging.

• Space complexity: Total space includes input storage and auxiliary space; algorithm comparisons usually emphasize auxiliary space.
• Recursion stack: A recursion depth of (d) consumes (O(d)) stack frames. Recursive depth-first search may require (O(V)) stack space for (V) vertices.
• Peak-memory rule: Space is the maximum simultaneously occupied memory, not the sum of every allocation made over time.
• Multiple parameters: Graph algorithms should retain meaningful variables. Breadth-first search is (O(V+E)), where (V) is the vertex count and (E) is the edge count.

VI. Resource Balancing — Choosing Between Competing Costs

A. Trade-off concept

A trade-off occurs when improving one property, commonly execution time, memory usage, simplicity, or accuracy, increases another cost.

1. Time versus space:

   • Recomputation: Calculate values when needed, reducing storage but increasing running time.
   • Memoization: Store previously computed results, increasing space to avoid repeated work.
   • For Fibonacci numbers, naive recursion takes exponential time and (O(n)) stack depth; memoization reduces time to (O(n)) while adding (O(n)) table space.

2. Preprocessing versus query time:

   • A prefix-sum array requires (O(n)) preprocessing and (O(n)) extra space.
   • Each range-sum query then takes (O(1)), compared with (O(n)) per query by direct scanning.
   • For (q) queries, the costs become (O(n+q)) and (O(nq)), respectively.

• Data-structure choice: An array offers (O(1)) indexed access, while a balanced search tree offers ordered insertion, deletion, and search in (O(\log n)).
• Exactness versus speed: Approximation can reduce computation, but competitive programming usually requires exact output unless an error tolerance is explicitly stated.
• Iteration versus recursion: Iteration often reduces stack usage; recursion may express tree and divide-and-conquer logic more clearly.
• Constant factors: For small limits, a simple (O(n^2)) algorithm may outperform a complex (O(n\log n)) implementation despite inferior asymptotic growth.
• Decision principle: Select the simplest correct algorithm whose worst-case time and peak memory fit the stated constraints with an adequate operational margin.