Give a big-Oh characterization, in terms of n, of the running time of the following method.
Give a big-Oh characterization, in terms of n, of the running time of the following method.
Related questions
Question
Give a big-Oh characterization, in terms of n, of the running time of the following
method.
![/** Insertion-sort of an array of characters into nondecreasing order +/
public static void insertionSort(char[] data) {
int n = data.length;
for (int k = 1; k<n; k++) {
char cur = data[k];
int j = k;
}
while (j> 0 && data[j-1] > cur) {
data[j] = data[j-1];
j--:
}
data[j] = cur;
// begin with second character
// time to insert cur=data[k]
// find correct index j for cur
// thus, data[j-1] must go after cur
// slide data[j-1] rightward
// and consider previous j for cur
// this is the proper place for cur](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F2ae76079-938b-4b5d-8ceb-1dfbc10f88ce%2F7e209f6b-6bc0-4f7b-a151-a83a50e9920c%2Fzub9oyn_processed.png&w=3840&q=75)
Transcribed Image Text:/** Insertion-sort of an array of characters into nondecreasing order +/
public static void insertionSort(char[] data) {
int n = data.length;
for (int k = 1; k<n; k++) {
char cur = data[k];
int j = k;
}
while (j> 0 && data[j-1] > cur) {
data[j] = data[j-1];
j--:
}
data[j] = cur;
// begin with second character
// time to insert cur=data[k]
// find correct index j for cur
// thus, data[j-1] must go after cur
// slide data[j-1] rightward
// and consider previous j for cur
// this is the proper place for cur
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 4 steps
