Advanced Algorithms Analysis: Comparing Sorting Programs A and B

Abstract

This report provides a detailed analysis and comparison of two sorting algorithms, A and B, executed on different computer systems, C1 and C2, with varying instructions per second. By examining the execution time required to sort arrays of different sizes, this study aims to determine the most efficient algorithm for sorting 100 and 10^6 numbers, considering the computational capabilities of the respective computer systems. The analysis is grounded in the computational formulas for each algorithm, with Algorithm A operating at a quadratic rate (2n^2 instructions) and Algorithm B at a linearithmic rate (50n log n instructions).

Introduction

Sorting algorithms are fundamental in computing for organizing data efficiently. This study focuses on comparing two distinct sorting algorithms to identify the more efficient algorithm under varying conditions. The efficiency is measured based on the number of instructions executed per second by two different computers, C1 and C2, highlighting the impact of computational power and algorithmic complexity on performance.

Problem

Assume that you have two sorting programs A and B to compare.

Get quality help now

Prof. Finch

Verified writer

Proficient in: Science

4.7 (346)

“ This writer never make an mistake for me always deliver long before due date. Am telling you man this writer is absolutely the best. ”

+84 relevant experts are online

Hire writer

The Program A is going to be executed on a computer C1 which executes 10 9 instructions per second and the program B is going to be executed on a different computer which can execute 107 instructions per second. Also assume that the program A executes 2n2 instruction to sort n items and the program B execute 50n log n instruction to sort the same number of inputs.

Q1. If you are to sort 100 numbers which algorithm you choose?

Q2. IF you are to sort 106 numbers which algorithm you choose?

Solution

Implementation of A Algorithm

If n = 100,

To sort 100 numbers, Algorithm A taken time = 2 x (100)2 / 109 seconds

=2 x 10-5 seconds

Algorithm taken time = Algorithm Execution Instruction / Machine Instruction Per Second

Advanced Data Structures 18404427

Implementation of B Algorithm

If n = 100,

To sort 100 numbers, Algorithm B taken time = ((50 x 100) x log 100) / 107 seconds

= ((5 x 103) x 6.

6) / 107 seconds

= 3.3 x 104 / 107 seconds

= 3.3 x 10-3 seconds

Solution Justification for Q1

The first question is required to sort 100 numbers using either A algorithm or B algorithm. Therefore, the user has calculated above to clarify that how much time will be taken to sort 100 numbers using A and B algorithms on the C1 and C2 computers separately. B algorithm has taken 3.3 x 10-3 seconds on the C2 machine where A algorithm takes 2 x 10 -5 seconds on the C1 machine to sort 100 numbers. According to the above calculations, A algorithm is executed faster on the C1 than the B algorithm executes on the C2 to sort 100 numbers, even it can be justified as follows.

Algorithm B taken time / Algorithm A taken time = 3.3 x 10-3 seconds / 2 x 10-5 seconds

= 1.65 x 102

= 165

Above calculation is shown that A runs 165 times faster than the B, therefore the A algorithm can be suggested for the first question.

Solution for Q2

➢ There are 106 numbers to sort.

Implementation of A Algorithm

If n = 106,

To sort 106 numbers, Algorithm A taken time = 2 x (106)2 / 109 seconds

= 2 x 1012 / 109 seconds

= 2 x 103 seconds

Advanced Data Structures 18404427

Implementation of B Algorithm

If n = 106,

To sort 106 numbers, Algorithm B taken time = ((50 x 106) x log 106) / 107 seconds

= ((5 x 107) x 19.9) / 107 seconds

= 9.95 x 108 / 107 seconds

=99.5 seconds

≈ 102 seconds

Solution Justification for Q2

The second question is required to sort 106 numbers using either A algorithm or B algorithm. Therefore, the user has calculated above to clarify that how much time will be taken to sort 100 numbers using A and B algorithms on the C1 and C2 computers separately. A algorithm has taken 2 x 103 seconds on the C1 machine where B algorithm takes approximately 10 2 seconds on the C2 machine to sort 10 6 numbers. According to the above calculations, B algorithm is executed faster on the C2 than the A algorithm executes on the C1 to sort 10 6 numbers, even it can be justified as follows.

Algorithm A taken time / Algorithm B taken time = 2 x 103 seconds / 102 seconds

= 2 x 10

= 20

Above calculation is shown that B runs 20 times faster than the A, therefore B algorithm can be suggested for the second question.

Conclusion

This report has justified solutions for both the questions that were requested to solve in the assignment. There are 2 algorithms such as 2n2 and 50n log n which runs on the C1 and the C2 machines respectively. Even though here 50 > 2, A algorithm depends on n2 where B algorithm depends on log n when the size of input grows. As well as not only the running time of an algorithm, computer hardware also a significant part to solve these problems. Because it will be taken small execution time with high machine instruction per second. The first question was required to sort 100 numbers using either A algorithm or B algorithm based on their execution time and the author has suggested B algorithm for the first question with proven calculations.

Then, A algorithm has been suggested for the second question after the comparison of the calculated answer. Therefore, this can be concluded as when there is a smaller size of inputs, the B algorithm will be taken lesser execution time to sort and the A algorithm would be perfect for the large number of inputs to sort.

Reference

1. Cormen, T. (2009). Introduction to algorithms. 2nd ed. Cambridge, Mass.: MIT Press.