Already have an account? Get multiple benefits of using own account!
Login in your account..!
Remember me
Don't have an account? Create your account in less than a minutes,
Forgot password? how can I recover my password now!
Enter right registered email to receive password!
Q. Calculate that how many key comparisons and assignments an insertion sort makes in its worst case?
Ans:
The worst case performance occurs in insertion sort occurs when the elements of the input array are in descending order. In that case, the first pass requires one comparison, the second pass requires two comparisons, third pass three comparisons till the kth pass requires (k-1), and in the end the last pass requires (n-1) comparisons. Therefore, we obtain the total numbers of comparisons as follows : f(n) = 1+2+3+.........+(n-k)+.....+(n-2)+(n-1) = n(n-1)/2 = O(n2)
The worst case performance occurs in insertion sort occurs when the elements of the input array are in descending order. In that case, the first pass requires one comparison, the second pass requires two comparisons, third pass three comparisons till the kth pass requires (k-1), and in the end the last pass requires (n-1) comparisons. Therefore, we obtain the total numbers of comparisons as follows :
f(n) = 1+2+3+.........+(n-k)+.....+(n-2)+(n-1)
= n(n-1)/2
= O(n2)
what are the charaterstics to determine weather an algorithm is good or not? explain in detail
This method is the reverse of FIFO and assumes that each issue of stock is made from latest items received in the enterprises .Thus if the last lot to be received is not sufficient
Multiplication Method: The multiplication method operates in 2 steps. In the 1ststep the key value K is multiplied by a constant A in the range O
What is A Container Taxonomy It's useful to place containers in a taxonomy to help understand their relationships to one another and as a basis for implementation using a class
Double ended queues are implemented along doubly linked lists. A doubly link list can traverse in both of the directions as it contain two pointers namely left pointers and righ
The number of different directed trees with 3 nodes are ?? The number of disimilar directed trees with three nodes are 3
Q. The reason bubble sort algorithm is inefficient is that it continues execution even after an array is sorted by performing unnecessary comparisons. Therefore, the number of comp
The controversy of RISC versus CISC never ends. Suppose that you represent an advocate for the RISC approach; write at least a one-page critic of the CISC approach showing its disa
write an algorithm to delete an element x from binary search with time complex
How does cpu''s part tming and controls generate and controls signls in computer?
Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!
whatsapp: +91-977-207-8620
Phone: +91-977-207-8620
Email: [email protected]
All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd