Question

Exercise 4–Timing Sorting AlgorithmCollect the run times for either selection sort or insertion sort (use random values for an array and sorted values; sorted the same list twice and collect time each time) for the following array sizes: 1000, 2000, and 10000. You should be able to confirm that the runtime is n^2 for unsorted list (i.e., going from 1000 to 2000 should be about 4 times slower and going from 1000 to 10000 should be about 100times slower).

Question 1: Does your sorting algorithm in exercise4run faster for a sorted listthan an unsorted list?Explain why or why not.

Question 2: What are some reasons for doing algorithm analysis and expressing running time in O notation?

Answer 1

Solution:-

So, let's understand the time complexity of section sort and insertion sort.

1. Well the time complexity of selection sort is O(n^2) in all cases.
2. Now for the insertion sort the time complexity is O(n^2) in worst case.

A) So for n= 1000

1TC (Time complexity) = n^2 =1000^2 = 10^6

B) For n =2000

2TC = n^2 = (2000)^2 = 4*10^6.

Therefore, 2TC/TC = 4 *10^6 / 10^6 = 4

Conclusion - So going from 1000 to 2000 it is 4 times slower it is confirmed.

2) Now similarly ,

For n =10000

3TC = n^2 = {10000)^2 = 10^8

Therefore,

3TC/TC = 10^8 / 10^6 = 1000.

Conclusion :- So it is confirmed that from 1000 to 10000 it is 10 times slower.

Question 1: Does your sorting algorithm in exercise4run faster for a sorted listthan an unsorted list?Explain why or why not

Answer:-

• Yes, the sorting algorithm runs faster for sorted list then and unsorted list because of the branch prediction.
• Branch prediction means it determines whether a conditional branch in the flow of instruction is executed or not.

Question 2: What are some reasons for doing algorithm analysis and expressing running time in O notation

Answer:-

• The time complexity of algorithms is commonly used big O notation.
• Its a asymptotic notation for time complexity.
• It represents the worst case of an algorithms complexity.So his is the main reason for algorithm analysis and expressing running time in O notation,
• Big O notation removes all constant factors so running time is calculated by in relation to N.