S6-P3

Question 1

166

Answer 1

2
A

Question 2

166 related:

When the array is already sorted, the ____ sorting algorithm is the best speed wise, and is of Order ____. The original sorting order and the desired sorting order (inc/dec) must be the same/doesn’t matter .

Answer 2

Insertion, O(n), same

Question 3

*

167

Answer 3

1
A
Note On Quick Sort (qs) Recursive Function: We use median as pivot for the best complexity order, when we find the median ( θ(n) ), we create the recursive tree, each side has n/2 numbers that the same process happens to them.

Reminder: Order of partition based on an element in an array is θ(n), because we’re finding the kth element in an array.

Question 4

168

Answer 4

3
A
Key phrase:جمله تقریبا مرتب

Question 5

168 related:

What’s the order of sorting K sorted list, each having n/k members?

Answer 5

O(All the elements (n) x log number of sorted lists (K))=O(n x logk)

Question 6

F this but read it to gain perspective

169

Answer 6

A

Question 7

End Of P3