Unit 1: Behaviour Analysis - Subjective Questions

Algorithm behaviour analysis is the study of how an algorithm uses computational resources and how its performance changes as the input size increases.

It is important in competitive coding because it helps programmers:

• Predict whether an algorithm will finish within the given time limit.
• Estimate the memory required for large inputs.
• Compare alternative solutions without implementing all of them.
• Identify bottlenecks such as nested loops, repeated calculations, or excessive memory allocation.
• Select an approach appropriate to the input constraints.

For example, if , an algorithm may require approximately operations and is generally impractical, while an algorithm is usually feasible.

Suppose algorithms have running-time functions and . Their relative growth can be studied using:

The result is interpreted as follows:

• If , then grows more slowly than .
• If , both functions have the same asymptotic growth rate.
• If , then grows faster than .

For example:

Therefore, grows more slowly than , making an algorithm asymptotically more efficient than an algorithm.

The three cases describe an algorithm's resource usage under different input conditions:

• Best case: The minimum work performed for any input of size .
• Average case: The expected work performed over inputs of size , based on an assumed probability distribution.
• Worst case: The maximum work performed for any input of size .

For linear search in an array of elements:

• Best case: The target is at the first position, requiring one comparison, so the complexity is .
• Average case: The target is typically found after approximately comparisons, so the complexity is .
• Worst case: The target is at the last position or absent, requiring comparisons, so the complexity is .

Worst-case analysis is commonly used because it provides a guaranteed upper bound on resource usage.

Common worst-case time-complexity classes, arranged from slower to faster growth, are:

Their typical meanings are:

• : Constant time, such as array indexing.
• : Logarithmic time, such as binary search.
• : Linear time, such as scanning an array.
• : Linearithmic time, such as merge sort.
• : Quadratic time, such as comparing every pair.
• : Cubic time, such as a basic all-pairs shortest-path algorithm.
• : Exponential time, such as enumerating all subsets.
• : Factorial time, such as enumerating every permutation.

Polynomial classes are usually more scalable than exponential and factorial classes.

Let represent an algorithm's resource usage and represent a reference growth function.

• Big-O: if constants and exist such that
  
  It gives an asymptotic upper bound.

• Big-Omega: if constants and exist such that
  
  It gives an asymptotic lower bound.

• Big-Theta: if positive constants , , and exist such that
  
  It gives a tight asymptotic bound.

For example, .

The number of inner-loop executions is:

Using the arithmetic-series formula:

In asymptotic analysis, constant factors and lower-order terms are ignored. Therefore:

The result is quadratic even though the inner loop does not execute times during every outer iteration. The total work is proportional to the triangular sum .

Loop structure determines how execution counts combine:

• Sequential loops: Their costs are added. If one loop takes and another takes , the total is .
• Independent nested loops: Their iteration counts are multiplied. Two loops that each run times produce work.
• Dependent nested loops: Their cost is expressed as a sum. If an inner loop runs times, the total is .
• Logarithmic loops: If a variable is multiplied or divided by a constant each iteration, the number of iterations is logarithmic. For example, repeatedly dividing by requires iterations.

The loop bounds and update expressions must therefore be examined instead of merely counting the number of loop statements.

Effectiveness means that an algorithm correctly solves the intended problem and terminates after a finite number of well-defined steps. It concerns correctness and suitability.

Efficiency means that the algorithm solves the problem while using acceptable computational resources, mainly execution time and memory.

The difference is:

• An effective algorithm produces the correct output.
• An efficient algorithm produces that output with reasonable resource usage.
• An algorithm may be effective but inefficient. For example, generating every permutation to solve a large optimization problem may be correct but have running time.
• An algorithm that is fast but produces incorrect results is not effective.

A strong competitive-coding solution must be both correct and efficient under the given constraints.

Practical efficiency is evaluated using several factors:

• Input size: The largest permitted value of .
• Time complexity: The growth rate of the number of operations.
• Space complexity: The growth rate of additional memory usage.
• Constant factors: Two algorithms in the same complexity class may perform differently because of operation costs.
• Data structures: Arrays, hash tables, trees, and heaps have different operation costs and memory requirements.
• Input and output cost: Slow input handling can affect programs that process large amounts of data.
• Language and environment: Execution speed, recursion limits, integer representation, and memory overhead vary.
• Input distribution: Average performance may differ from worst-case performance.

Asymptotic analysis guides the initial choice, while benchmarking and constraint analysis help confirm practical suitability.

A recurrence relation expresses the cost of a recursive problem in terms of smaller instances. For binary search, each call examines one middle element and continues with half of the array.

The recurrence is:

After recursive calls, the remaining problem size is:

Recursion ends when this value becomes :

Therefore:

Since each level performs constant work, the total time complexity is:

A recursive implementation also uses stack space, while an iterative implementation can use auxiliary space.

Space complexity measures how the memory required by an algorithm grows with the input size .

• Total space includes the memory occupied by the input, output, program variables, dynamically allocated structures, and recursion stack.
• Auxiliary space includes only the extra memory used by the algorithm apart from the input and required output.

For example, merge sort uses an additional temporary array of size , so its auxiliary space is . An in-place selection sort uses only a constant number of extra variables, so its auxiliary space is .

Recursive calls must also be included in auxiliary-space analysis. A recursion depth of generally requires stack space.

The algorithms have different time-space characteristics:

Merge sort:

• Divides the input recursively and merges sorted halves.
• Scales well for large input sizes.
• Requires temporary storage during merging.

Selection sort:

• Repeatedly selects the smallest remaining element.
• Uses very little additional memory.
• Performs approximately comparisons.

Thus, merge sort is generally preferable when execution time is important and additional memory is available. Selection sort may be considered for small inputs or strict memory constraints.

The time-space trade-off is the principle of using additional memory to reduce execution time, or accepting more computation to reduce memory usage.

A common example is checking whether values have appeared before:

• Without extra storage, each new value can be compared with all earlier values. This may require time and auxiliary space.
• With a hash set, each value can be inserted and queried in expected time. The complete process takes expected time but uses extra space.

Another example is dynamic programming, where previously computed results are stored to avoid repeated recursive calculations.

The correct choice depends on:

• The input size.
• The memory limit.
• The time limit.
• Whether the data structure's worst-case behaviour is acceptable.

The naive Fibonacci recurrence is:

A direct recursive implementation recalculates the same subproblems many times. Its recursion tree grows exponentially, giving approximately time and stack space.

With memoization, each value is computed once and stored:

• There are only distinct subproblems.
• Each subproblem performs constant work apart from recursive calls.
• Time complexity becomes .
• The memoization table uses space.
• The recursion stack also uses space.

This demonstrates a time-space trade-off: additional memory reduces repeated work and changes exponential running time into linear running time.

Asymptotic analysis focuses on how resource usage grows as becomes large. The highest-growth term eventually dominates lower-order terms.

For example:

As increases, the term dominates, so:

The coefficient and terms are ignored because they do not change the growth class.

However, constant factors still matter in practice when:

• Input sizes are small or moderate.
• Two algorithms have the same asymptotic complexity.
• One algorithm uses expensive operations.
• Cache behaviour and memory access patterns differ.
• Time limits are strict.

Thus, asymptotic analysis is essential for scalability, but practical measurements remain useful.

Let the loop variable take the values:

The loop stops when . Therefore, the number of iterations is:

During every iteration, the algorithm performs an scan. Hence, the total cost is:

Therefore:

If the scan uses only a fixed number of variables, its auxiliary-space usage is . If it stores data proportional to , the space complexity must be adjusted accordingly.

Worst-case analysis determines the maximum resources an algorithm can require for any valid input of size .

It is preferred because:

• Online judges may include adversarial or specially constructed test cases.
• It provides a guaranteed upper bound on execution time and memory.
• It does not require assumptions about input probability distributions.
• It helps determine whether a solution can meet strict limits for every valid test.
• It supports reliable comparison between algorithms.

Its limitations include:

• It may describe inputs that occur rarely in real applications.
• It may hide strong average-case performance.
• Big-O bounds may be loose rather than exact.
• It does not directly capture constants, cache effects, or implementation overhead.

Worst-case analysis should therefore be combined with tight bounds, constraint checks, and practical testing.

Asymptotically, grows more slowly than because:

Therefore, the algorithm is generally more scalable.

However, an algorithm can be faster for small inputs when:

• It has a much smaller constant factor.
• It has simpler control flow.
• It uses contiguous memory efficiently.
• The algorithm requires recursion or expensive data structures.
• Setup costs dominate execution.

This is why insertion sort is often used for small subarrays inside advanced sorting implementations. Complexity class predicts long-term growth, while actual speed also depends on constants and hardware behaviour.

Approximate operation counts help evaluate feasibility:

• : About operations. This is normally suitable.
• : Using , the count is roughly . This is normally suitable.
• : About operations. This is generally too slow for standard time limits.
• : The operation count is astronomically large and entirely infeasible for .

These estimates are guidelines rather than exact guarantees. Practical feasibility also depends on:

• The constant amount of work per operation.
• The programming language.
• The time limit.
• Input and output overhead.
• Hardware and memory-access behaviour.

For , competitive-programming solutions usually target or .

A systematic selection process includes the following steps:

1. Understand correctness requirements: Identify the required output, edge cases, and numerical limits.
2. Read the constraints: Determine maximum input size, time limit, and memory limit.
3. Estimate acceptable complexity: For large , reject growth rates that produce impractical operation counts.
4. Analyse candidate algorithms: Determine worst-case time and auxiliary-space complexities.
5. Check data structures: Include their operation costs and memory overhead.
6. Consider trade-offs: Decide whether preprocessing, caching, or memoization justifies additional memory.
7. Account for implementation details: Examine recursion depth, integer overflow, input-output cost, and constants.
8. Test boundary cases: Measure performance near maximum constraints.

The selected algorithm must first be correct, then satisfy both limits in its worst credible execution scenario.