Scribd
Upload
15 views9 pages

Sorting Algorithm Performance Analysis

The document compares the execution times of Bubble Sort and Insertion Sort against Merge Sort and Quick Sort as the number of elements increases. It highlights that Bubble Sort and Insertion Sort exhibit a dramatic increase in execution time due to their O(n²) complexity, while Merge Sort and Quick Sort scale efficiently with O(n log n) complexity. The execution times for various values of n illustrate the significant performance differences between these sorting algorithms.

Uploaded by

Anand K
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views9 pages

Sorting Algorithm Performance Analysis

The document compares the execution times of Bubble Sort and Insertion Sort against Merge Sort and Quick Sort as the number of elements increases. It highlights that Bubble Sort and Insertion Sort exhibit a dramatic increase in execution time due to their O(n²) complexity, while Merge Sort and Quick Sort scale efficiently with O(n log n) complexity. The execution times for various values of n illustrate the significant performance differences between these sorting algorithms.

Uploaded by

Anand K
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Data Structures

Assignment-3

1)
Bubble Sort and Insertion Sort show a dramatic increase in execution time as the number of
elements increases. For example:
o At 𝑛 = 100, both take effectively 0 s.
o At 𝑛 = 1,000, Bubble Sort takes 0.043 s, while Insertion Sort is faster at 0.013
s.
o At 𝑛 = 10,000, the times jump to 4.57 s for Bubble Sort and 2.06 s for
Insertion Sort.
o For 𝑛 = 100,000, Bubble Sort becomes extremely slow at 958 s, and
Insertion Sort takes 229 s.
This behaviour is consistent with their O(n²) complexity. As 𝑛increases, the number of
comparisons and shifts grows quadratically, causing the steep rise in time.
Merge Sort and Quick Sort, on the other hand, scale much more efficiently:
o At 𝑛 = 1,000, Merge Sort takes 0.008 s and Quick Sort only 0.0015 s.
o For 𝑛 = 10,000, Merge Sort requires 0.027 s, while Quick Sort takes 0.016 s.
o Even for 𝑛 = 100,000, Merge Sort completes in 0.373 s, and Quick Sort in
just 0.194 s.
These results align with their O(n log n) complexity. The number of operations grows much
more slowly than in quadratic algorithms
2)
3)

You might also like