Please help me with this questions Thank you 50 Short Answer

Please help me with this questions. Thank you.

[50] Short Answer

1.[10] Give (A) a name of one of the comparison-based sorting algorithm and

(B) its asymptotic upper bound (O) of running time in the worst case.

2.[10] What is the smallest number of internal nodes of a heap of height h? Explain your answer by drawing a heap.

3.[10] In a proper binary tree, prove that e 2^h where e is the number of external nodes and h is the height of tree.

4.[10] For a given record of 100 patients, you’re trying to sort the patients according to their birth of date () in non-decreasing order: e.g.) 19890605 (i.e. 1989-June-5^th). What do you think is the best sorting algorithm to sort the records? Justify your answer.

5.[10] Decide the asymptotic upper bound (O) of f(n) and prove it by the definition of big-Oh.

Solution

Answer 1

Bubble sort is one of the example of comparison based sorting algorithm.

It sorts the array by comparing each element with the remaining other.

The complexity of the bubble sort is O(n) as there are it take square time to solve and sort the array.