Page 135 - Data Structures Handout_Neat

10.5 Performance Analysis

Sorting algorithms are evaluated based on their time complexity, space complexity,

and stability. These factors determine how efficient an algorithm is for different datasets and

scenarios. While some algorithms are simple but slow, others are complex but highly efficient.

Understanding performance analysis helps in choosing the right algorithm for a given

problem.

10.5.1 Time Complexity

Time complexity measures how the running time of an algorithm grows with the size

of the input . Sorting algorithms vary widely in their performance:
2
• Bubble Sort, Selection Sort, Insertion Sort: Worst-case ( ).
• Merge Sort, Quick Sort, Heap Sort: Average-case ( log⁡ ).

• Counting Sort, Radix Sort: Linear time ( )under certain conditions.

10.5.2 Space Complexity

Space complexity measures the amount of extra memory required by an algorithm:
• In-place algorithms (Bubble, Selection, Insertion, Quick, Heap): (1)extra space.

• Merge Sort: Requires ( )extra space for merging.

• Counting Sort and Radix Sort: Require additional arrays proportional to the range
of values or number of digits.

135