Register

Cormen Edition 3 Exercise 1.2 Question 2 (Page No. 14)

631 views
0 votes
0 votes
Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n$, insertion sort runs in $8n^2$ steps, while merge sort runs in $64\ n \lg n$ steps. For which values of $n$ does insertion sort beat merge sort?
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
akash.dinkar12 asked Jun 25, 2019
389 views
Cormen Edition 3 Exercise 1.2 Question 3 (Page No. 14)
What is the smallest value of $n$ such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?
What is the smallest value of $n$ such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?
User Avatar
0 votes
0 votes
0 answers
2
akash.dinkar12 asked Jun 25, 2019
146 views
Cormen Edition 3 Exercise 1.2 Question 1 (Page No. 14)
Give an example of an application that requires algorithmic content at the application level, and discusses the function of the algorithms involved.
Give an example of an application that requires algorithmic content at the application level, and discusses the function of the algorithms involved.
User Avatar
0 votes
0 votes
1 answer
3
akash.dinkar12 asked Jun 28, 2019
1,253 views
Cormen Edition 3 Exercise 9.1 Question 2 (Page No. 215)
Prove the lower bound of $\lceil 3n/2\rceil – 2$ comparisons in the worst case to find both the maximum and minimum of $n$ numbers. (Hint: Consider how many numbers are potentially either the maximum or minimum and investigate how a comparison affects these counts.)
Prove the lower bound of $\lceil 3n/2\rceil – 2$ comparisons in the worst case to find both the maximum and minimum of $n$ numbers. (Hint: Consider how many numbers are...
User Avatar
Link Copied!