Harvard University Programming Asymptotic Notation Questions

Please find attached

(c) A child is sorting her favorite toys in order of preference, from least favorite to most favorite. She
has never learned about sorting algorithms. So she comes up with her own idea. She lays out all the n
toys in a row from left to right on her bedroom floor. She starts by standing in front of the two left-most
toys and carries out the following: if the two toys directly in front of her are in the wrong relative order,
she swaps them, and then steps to the left (as long as there are toys on that side). Otherwise, she steps to
the right. She repeats this step this until she reaches the right-most toy and doesn’t carry out any swaps.
Justify why her technique correctly sorts the toys. What algorithm from class is she executing?
*A figure is included at the end of the assigment
(d) For each of the following f(n), show that f(n) is (g(n)) for the correct function g(n). Prove your
result using the definitions from class, including an explicit value for k justifying your statement is true
for all n > k.
=
21.5
f(x) = neº log(2n) + nº log(n) + Vn
f(n) = 2″ .na + 100 – 3″ +n4
Question 6: Lower Bounds and Linear time Sorting
• (a) A set of n natural numbers are uniformly distributed in the range 1 < x < Vn. Determine the runtime (in big-Theta notation) of Counting Sort and Radix Sort. Find the expected runtime of Bucket sort using 10 buckets. Which algorithm has the best asymptotic runtime? (b) Given a set of three numbers {a,b,c} draw the comparison-based decision tree that represents the execution of bubble-sort. Justify the length of the longest-path in your tree, using the results of problem 5 from practice set 1. 4 Figure for problem lc: Below shows one step of the girls sorting process. Examining bears 5 and 1, she decides they need to be swapped. Then she moves left and will examine bears 4 and 1 next.