Question 1 (40 points) the truth of each of the following statements. Cirole (o)

Question

Question 1 (40 points) the truth of each of the following statements. Cirole (o) the number if it is and cross the 1. The best-case running time of the merge sort algorithm is O(n x u worst-case running time O(n2), where n is the array size. is n), and th 2. The quick-sort algorithm is in-place, but the merge-sort algorithm is not in plac 3. The worst-case running time of insertion-sort is on?), and the best-case runni time is where n is the array size 4. alog nlogg n+1 6. For any two functions f(n) and g (m), f(m) n(g(n)) if g (m) n f(n) 9. If T(m) (m/2) na, T(1) 1, then T(n) o(na).

Explanation / Answer

Answer:

1. False , because the merge sort is the only algorithm which has best , worst and average case O(nlogn) not O(n).

2. True , because we do not require extra space for quick sort but for merge sort , we need extra space like to merge two arrays , we need an extra array to merge two arrays.

3. True, insertion sort has O(n^2) because number of comparisons and swaps.

4. n^log a = a^logn

apply log on both sides , we get

log(n^loga) = log(a^logn)

loga * logn = logn *loga

loga * log n = loga *logn ( so both are equal) , True

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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