Question

1. Write the forpseudocode  an algorithm that determines if a function is injective, assuming that you can iterate through all the elements in the domain and the co-domain in a finite number of steps.
   
2. Recall the insertion sort algorithm discussed in class (pseudocode shown below).  Find the big-O of the number of comparisons made in the execution of insertion sort on the input list of numbers:  k, k-1, k-2, ..., 2, 1.  Explain your reasoning.

ALGORITHM 5 The Insertion Sort.

procedure insertion sort(a1, a2, ..., : real numbers with n > 2) for j = 2 ton i=1 while aj > a i=i+1 m = 0; for k:= 0 to j-i-1 aj-k := 0;-k-1 dim {a1, ..., An is in increasing order)

5.

1. Find the O(g) estimate for each of the following functions. The order of g should be as small as possible, and g should be as simple as possible.
2. a) nn100+nn(n!)+n1.2n

b) (n5+100)(32 log n - 6) + log n (n5 + 2n4 log n)

c) (n6+1.5n)(1.1n+n5)

Answer 1

2.

To insert the last element, we need at most n-1 comparisons and at most n-1 swaps. To insert the second to last element, we need at most n-2 comparisons and at most n-2 swaps, and so on. The number of operations needed to perform insertion sort is therefore: 

$2(1+2+ \dots +n-2+n-1)=\frac{2(n-1)(n-1+1)}{2}=n(n-1)$

So, the algorithm's complexity is $O(n^2)$

5.1

b)

$f(n)=(n^5+100)(32 log n - 6) + log n (n^5 + 2n^4 log n)=$

$=32n^5logn+3200logn-6n^5-600+n^5logn+2n^4logn\le3841n^5logn$

$f(n)=O(n^5logn)$

c)

$f(n)=(n^6+1.5n)(1.1n+n^5)=1.1n^7+n^{11}+1.65n^2+1.5n^6\le5.25n^{11}$

$f(n)=O(n^{11})$

a)

$f(n)=nn^{100}+n^n(n!)+n1.2^n\le 3n^n(n!)\le3n^nn^n=3n^{2n}$

$f(n)=O(n^{2n})$

1.

input:

int n \\ the number of values

array x(n) \\ domain of function f(x)

array f(n) \\ values of function f(x)

for i from 1 to n

for j from 1 to n

if f[i]=f[j] then

break

output:

function is not injective

else

function is injective