文档介绍：Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in (64n 1g n) steps. For which values of n does insertion sort beat merge sort?
Answer: if we want the insertion sort beat the merge sort, the condition that should be satisfied with is: 8n2 v 64n 1g n n < 81gn
2n v n8
llinclude <stdio .h>
ttinclude <>
int main(int argcv char »argv[]) < int n-1000,1vcount m0;
double x ;
For( i-1; i < n; !♦♦)
x - pow(2vi);//x - y ■ pow(i v8);//y .
•M)；
< y)< printFC n- count**;
if(cuunt % 5»»0)printf CAn**) ;//5 element a line
printf(,,\ne,);
return 0;
■华:区一两学期\c语言程序\Debug\
n=
2
n= 3
n= 4
n=
5
n= 6
n=
7
n= 8
n= 9
n=
| 10
n= 11
n=
12
n= 1
3 n=
14
n=
15 n= 16
n=
17
n=】
8 n=
E
n=
20 n= 21
n=
22
n= 2
3 n=
24
n=
25 n= 26
n=
27
n= 2
18 n=
29
n=
30 n= 31
n=
32
n= 3
3 n=
34
n=
35 n= 36
n=
37
n= S
|8 n=
39
n=
40 n= 41
n=
42
n= 4
Press any key to continue
2<= n v =43
So when n range from 2 to 43, the insertion sort beat the merge sorto
Algorithm Mystery(A: Array of integer)
if i=j then return A[i]
else
k=i+floor((j・i)/2)
templ= Mystery(A[i..k]]
temp2= Mystery (A [ (k+1}.. j ]
if templ<temp2 then return tempi else return temp2
What does the recursive algorithm above compute?
Determ