Think Pair Share 29

Think

Insert a new row just below the header in the table in your TPS Google Doc. Fill in the first two columns. Place your response to the following in the "Think" column:

We discussed a few sorting algorithm last class: bubble sort, selection sort, and insertion sort. You read about the latter two. Each of these have a time complexity of $O\left(n^2\right)$, where n is the number of things in the list being sorted. When we discussed searching, we learned that linear search has a time complexity of $O\left(n\right)$ since potentially ever item in the list needs to be checked, while binary search has a time complexity of $O\left(\log_2\left(n\right)\right)$, but only works if the list is already sorted. Further more, saw that if we had all 7 billion people on earth lined up in order of name, it would have to ask no more than 33 people what their names were in order to either find someone we're looking for or discover that there weren't in the list.

The question is, how expensive is it to get all 7 billion people on earth sorted using one of the aforementioned search algorithms? How many searches would we need to perform with linear search over the unsorted version before it would be more efficient to sort and then use binary search?

Pair

If you are joining the class live (in person or over Zoom), pair up with someone when asked to do so—please use Discord or your preferred means of interacting with someone to share your answers (please see the announcement with details about Discord).  Settle on an answer between to two or three of you and put that answer down in your "Pair" column.

Share

Regardless of whether or not you are attending live, one person from your pair group should add your answer to the "TPS class share Links to an external site." document.

Submit

Finally, submit your personal TPS Google doc to this assignment.