week 10

Question 1

worst case running time of quicksort
( not actually the quickest of the sorts despite name)

Answer 1

0(n^2)

Worst-case Running Time
The worst case for quick-sort occurs when the pivot is the unique
minimum or maximum element
One of L and G has size n - 1 and the other has size 0
The running time is proportional to the sum
n + (n - 1) + … + 2 + 1
Thus, the worst-case running time of quick-sort is O(n^
2
)

bad luck again and again and again

Question 2

best case running time of quick sort

Answer 2

0(nlogn) - same as merge sort

Question 3

time complexity of merge sort

Answer 3

0 (n log n);

merge sort breaks down the sequence by 2 each level until you get a sequence with one element

1st level - n
2nd level - n/2 + n/2 ( 2 sequences to merge)
3rd= n=4 + n/4 +n/4 + n/4
.
.
.

n elements and 2^ h boxes ( h - height) at each level

2^k = n
k = log n

merging n elements so n x logn