Section 3.1: How many comparisons does the insertion sort use to sort the list n

Question

Section 3.1: How many comparisons does the insertion sort use to sort the list n, (n - 1), (n - 2), ..., 2, 1? 2. Section 3.2: Determine whether each of these functions is O(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 Section 3.2: For each of the above, determine if they are Ohm(x^2) and whether if they are theta(x^2). Section 3.3: 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

Consider n=1,

The loop1 I=1 and I<=1 and inner loop j<=i so it executes for 1 time .

Consider for n=2.

Outerloop executes for 2times and inner loop for 1 time when j=1 loop executes when ,j=2,2is not less than 1 so total 3times

When n=3,the loop executes for 6times

So the count will be in series 1,3,6,10,15

I.e for n numbers num of operations is n(n+1)/2

Simplifying it comes to (n^2+n)/2 I.e order of n^2

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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