JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech III ALGORITHM DESIGN AND ANALYSIS Previous Question Paper (August - 2022 - R18)

Performance analysis is the process of determining the resources required by an algorithm to complete its execution. It primarily focuses on two metrics: Space Complexity and Time Complexity.

Space complexity represents the amount of memory an algorithm needs to run to completion. It consists of a fixed part (constant space for variables, constants, and instructions) and a variable part (dynamic memory allocation, recursion stack space). It is expressed as S(P) = C + S_p(n).

Time complexity represents the amount of computer time required by an algorithm to run to completion. It is analyzed by counting the frequency of operations, specifically the basic operations that dominate the execution time. It is expressed as T(P) = C + T_p(n). Performance analysis is typically evaluated using asymptotic notations like Big O, Omega, and Theta to describe the growth rate of resource consumption as the input size n increases.

Quick Sort is a divide-and-conquer algorithm that picks an element as a pivot and partitions the array around it. The process involves selecting a pivot, reordering the array so that elements smaller than the pivot are on the left and larger are on the right, and recursively sorting the sub-arrays.

Steps for implementation:

1. Choose an element as the pivot (e.g., the last element).
2. Partition the array: maintain two pointers, i and j, to swap elements such that all elements less than the pivot move to the left side.
3. Place the pivot in its correct sorted position.
4. Recursively apply the same logic to the left and right sub-arrays.

Example: Consider the array [24, 9, 29, 14, 19].

1. Select 19 as the pivot.
2. Partitioning: Compare 24, 9, 29, 14 with 19. After swapping, the array becomes [14, 9, 19, 29, 24].
3. 19 is now in its sorted position.
4. Recursively sort [14, 9] and [29, 24].
5. Result: [9, 14, 19, 24, 29].

The average time complexity is O(n log n), while the worst-case complexity is O(n^2) when the pivot selection is poor (e.g., already sorted array).