1. Answers
  2. Computer Science
  3. Discrete Mathematics
  4. Write the forpseudocode an algorithm that determines if a function is injective, assuming that you …
Solution to Write the forpseudocode an algorithm that determines if a function is injective, assuming that you … - Sikademy
Author Image

Archangel Macsika

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. 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. 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. 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)

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Join our Community

Question ID: mtid-5-stid-8-sqid-947-qpid-802