6. (11 pts) Starting at the page 24 (Analysis of Insertion Sort), the text descr

Question

6. (11 pts) Starting at the page 24 (Analysis of Insertion Sort), the text describes a method of producing a formula for the growth rate of an algorithm and using that formula to calculate the bounds of the growth rate (best and worst case) for the that algorithm. This process was also discussed on the first day of the lectures. Use the same method to compute the running time T(n) of the following algorithm (Let length[A].) by using a variable such as t or tj, i.e., first provide a general running time T(n). Then show the running time T(n) for each of the best case and the worst case. Also express the number of times that each line is executed using n- length[A], in the following table constant times cl FUNCTIONI (A) //A is an array of length n 1) n-length[A] 2) count-0 3) for (i=1;i

Explanation / Answer

Solution:

First, we will see how each line will be executed and how much time it will take.

C1 = O(1), means constant time

C2 = O(1), means constant time

C3 = O(n), the loop is running n number of times

C4 = 1+2+3+4+5+6+7+......n = n(n+1)/2 = O(n^2)

C5 = O(1), this line will take constant time but it will be running O(n^2) since it is in the loop.

C6 = O(n^3)this loop is running O(n^3) times

C7 = O(1), constant time

C8 = O(1), constant time

C9 = O(1), constant time

Best case:

Best case will happen when the third loop won't get a chance to run and the time complexity of the given function A will be

T(n) = O(n^2).

Worst case:

In worst case the last loop with k variable will be running and the time complexity of function A will be

T(n) = O(n^3)

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

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