To install StudyMoose App tap and then “Add to Home Screen”
Save to my list
Remove from my list
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).
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.
Assume that you have two sorting programs A and B to compare.
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. ”
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?
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
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.
➢ 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
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.
| Algorithm | Execution Time (seconds) |
|---|---|
| A | 2 x 10^3 |
| B | 10^2 |
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.
Advanced Algorithms Analysis: Comparing Sorting Programs A and B. (2024, Feb 23). Retrieved from https://studymoose.com/document/advanced-algorithms-analysis-comparing-sorting-programs-a-and-b
👋 Hi! I’m your smart assistant Amy!
Don’t know where to start? Type your requirements and I’ll connect you to an academic expert within 3 minutes.
get help with your assignment
