How many comparisons does the insertion sort use to sort the list n, (n - 1), (n

Question

How many comparisons does the insertion sort use to sort the list n, (n - 1), (n - 2), ..., 2, 1? Determine whether each of these functions is 0(x^2) a) f(x) = 10 b) f(x) = x^2 + 100 c) f(x) = x log x d) f(x) = x^2/2 e) f(x) = 2^x For each of the five functions above, determine if they are Ohm(x^2) and whether if they are Theta(x^2). Give Phi-notation for the number of arithmetic operations performed by the following code. Explain how you got your answer: t: = 1 for i: = 1 to n for j = 1 to i t: = t + 1

Explanation / Answer

3.

b f(x)=x^2 +100

c.f(x)=(x^2/)2

in asymptotic analysis we ignore constants since for greater values of x these constants will have negliigible values as compared to x^2 term and thus won't influence the ultimate result.

hence we can write

b. f(x)=x^2

c.f(x)=x^2

both are theta(x^2) becuase no matter what they are going to grow with rate of x^2.

4.

t=1 theta(1) i.e it constant it is executed only once.

for i=1 to n theta(n+1) it is executed n + 1 times 1 for checking if i>n

for j=1 to i theta(n) all the things in side a loop are executed the number of times that loop executes

t=t+1 theta(n*i) all the things in side a loop are executed the number of times that loop executes times outer loop.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.