Question

Show that insertion sort has worst case performance O(N2)

Show that insertion sort has worst case performance O(N2)

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Insertion sort has worst case performance as O(N2) when input array is already sorted but in non-ascending order.

For example consider the array below.

N N-1 N-2 ............. 6 5 4 3 2 1

1st Element N will not be compared with anyone => 0 Comparisons.

2nd Element N-1 will be compared to N. N-1 and N will be swapped => 1 comparison

N-1 N N-2 ............. 6 5 4 3 2 1

3rd Element N-2 will be compared to N. N-2 and N will be swapped then N-2 will be compared with N-1. N-1 and N-2 will be swapped. => 2 comparisons

N-2 N-1 N ............. 6 5 4 3 2 1

Similarly

(N-1)th element 2 will be compared to N, N-1, N-2, ... 3 => N-2 Comparisons

Nth element 1 will be compared to N, N-1, N-2, ... 2 => N-1 Comparisons

1 2 3 4 5 6 ........... N-2 N-1 N

So, total number of comparisons

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Give a worst-case input sequence of 6 numbers for Insertion Sort, containing the numbers 21, 16,...
Give a worst-case input sequence of 6 numbers for Insertion Sort, containing the numbers 21, 16, 77, 3, 8, and 11.No explanation/proof required.
Show that the worst case of the Quicksort is Ω(n2)
Show that the worst case of the Quicksort is Ω(n2)
Sorting – Insertion Sort Sort the list 0, 3, -10,-2,10,-2 using insertion sort, ascending. Show the...
Sorting – Insertion Sort Sort the list 0, 3, -10,-2,10,-2 using insertion sort, ascending. Show the list after each outer loop. Do this manually, i.e. step through the algorithm yourself without a computer. This question is related to data structure and algorithm in javascript (.js). Please do not copy from stackabuse or stackoverflow, Please explain that algorithm with comments. i really want to learn this concept.
#data structures Give the appropriate execution time efficiency of the following array algorithms using Big-O notation....
#data structures Give the appropriate execution time efficiency of the following array algorithms using Big-O notation. Assume the size of the array is n. a)   Linear Search (average case)   ______________________    b)   Binary Search (worst case)       ______________________    c)   Insertion Sort (best case)       ______________________    d)   Insertion Sort (average case)           ______________________    e)   Quick Sort (average case)           ______________________
What is the worst – case performance of Quicksort? Prove it.
What is the worst – case performance of Quicksort? Prove it.
void insertion_sort(element a[], int n) // Put a[0]..a[n-1] into ascending order by insertion sort. { for...
void insertion_sort(element a[], int n) // Put a[0]..a[n-1] into ascending order by insertion sort. { for (int k = 1; k < n; k++) { // At this point, a[0]..a[k-1] are already in order. // Insert a[k] where it belongs among a[0]..a[k]. You need to write code for this insertion as the body of the for-k loop. } //endfor k } a) Write the code for the body of the for-k loop to complete the insertion sort routine. b) Count...
Consider the following insertion sort algorithm. void insertion_sort(element a[], int n) // Put a[0]..a[n-1] into ascending...
Consider the following insertion sort algorithm. void insertion_sort(element a[], int n) // Put a[0]..a[n-1] into ascending order by insertion sort. { for (int k = 1; k < n; k++) { // At this point, a[0]..a[k-1] are already in order. // Insert a[k] where it belongs among a[0]..a[k]. You need to write code for this insertion as the body of the for-k loop. }//endfor k } a) Write the code for the body of the for-k loop to complete the...
What is the worst-case time (in Big-O) for building a Min-Heap of N nodes, using bulk...
What is the worst-case time (in Big-O) for building a Min-Heap of N nodes, using bulk insertion (bottom-up construction), assuming comparing two keys takes constant time. Justify your answer. You may assume N = 2h+1 – 1, for simplicity.
(4 pts) What is the worst-case Big-O of the insert () algorithm for the red-black tree?...
(4 pts) What is the worst-case Big-O of the insert () algorithm for the red-black tree? Explain. (4 pts) What is the worst-case Big-O of the remove () algorithm for the red-black tree? Explain. (2 pts) What is the worst-case Big-O of the clear () algorithm for the red-black tree? Explain.
H. The practical worst case performance level is the optimum level of performance that is used...
H. The practical worst case performance level is the optimum level of performance that is used to evaluate the actual performance of the line and it is fixed when the amount of work in process is changed
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT