Sorting!

 This week I learned the formal definition of O(n²). The formal definition is when n is beyond breakpoint B, f(n) is upper-bounded by cn², where c is come chosen constant multiplier. Ω(n²) is the set of functions that grow no slower than n². Ɵ(n²) is the set of functions that are both O(n²) and Ω(n²).

A fairly intuitive thing that I learned in the lectures this week was that functions similar to nⁿ grow fast and functions similar to log (n) grow slowly.

The sorting algorithm introduced this week was fairly simple, since it was review. I learned a variety of sorting algorithms in high school, such as merge sort, quick sort, insertion sort, etc. I the lecture Prof. Heap went over insertion sort. Insertion sort grows a sorted list within an unsorted list. In each insertion an element is removed from the unsorted portion of the list and inserted within the sorted portion.

One thing I found really surprising was that the loop guard adds one step each time a while loop stops iterating. In addition, lines outside the loops add one step and are constant. Another thing that surprised me was that summation is used to create a formula for worst case running time.

I also learned what a maximum splice function does this week. Maximum splice enumerates all possible slices of a list and calculates the sum of each slice, returning the max. Also, when finding the upper-bound it is okay to overestimate the number of steps and when finding the lower-bound it is okay to underestimate the number of steps.

This week I did the folding problem solving problem. First, I read over the problem and made sure I understood it. The problem asks if I can arrange pennies from two drawers, so that one of them have 48 pennies, using two operations, 1 and r. Secondly, I came up with a plan. My plan was to make a tree of what arrangements I could come up with. Then I would work backwards from 48 and try to get to one of the arrangements that have been confirmed.