Homework 7, Part A: Big-O

Learning Goals

Understanding the Big-O complexity at the level of individual statements and methods

Task: Find the running time of statements in a method

Consider the following method that removes a CD from a linear collection (e.g. array).

code to remove a CD from an array

Assume that the collection has n CDs to start with. Answer each of the questions below. Provide your answer by writing a sentence for each question, and then explaining the Big-O notation associated with the relevant statement.

Note: If you find any of the Questions ambiguous (that is, it may mean two different things and you are not sure which one is the correct interpretation), explain why and give your answer for each alternative.

Write your answer in a text file called BigO.txt (not a Word .doc or some other special format—just plain text) and submit it in the proper assignment folder.

Homework 7, Part B: Trace Sorting by hand

Learning Goals

Gain a detailed understanding on how sorting algorithms work
Working with best-known sorting algorithms

Exercise: Trace Sorting Algorithms

Complete the following questions on paper by hand, scan them as a PDF, and submit as the file SortingTrace.pdf to Gradescope.

Given the following array of numbers:

255 31 15 127 511 1023 63 7 2047

Show a trace of execution for each of the sorting methods as shown in the book:

selection sort (listing 13.5, page 492)
insertion sort (listing 13.5, page 493)
merge sort (listing 13.5, page 495)

The meaning of “trace” depends on each sorting method.

For selection sort, it means to display the contents of the array at every selection.
For insertion sort, it means to display the contents of the array after each insertion.
For mergesort, it means to draw the two trees that are created by splitting and merging.

What to submit

Make sure you title your paper and you write your name(s) on the document you are submitting.
Create a PDF file named SortingTrace.pdf by scanning the completed worksheet and submit to Gradescope.

Submission Checklist

You submitted all .pdf files and all .txt files.
Your files are named exactly as in the homework specification, including file extensions.