Activity 02: Sorting 2

Learning Goals

You will work towards being able to…

  1. Formalize algorithmic ideas into pseudocode
  2. Compute growth functions from time & space complexities under the RAM model
  3. Determine the Big-O, big-$\Omega$, and big-$\Theta$ time complexities of algorithms
  4. Know common algorithms to solve cannonical problems (sorting)

Instructions

  1. Look back at the pseudocode you’ve written for Activity 1 (check your Moodle submission)

  2. Determine an explicit growth function for your pseudocode’s worst-case time complexity. If the sort algorithm you found is suspiciously similar to insertion sort, take a moment to chat with an adjacent group and acquire a copy of their pseudocode

  3. Use your prior background from COMP128 to speculate about the big-Oh time complexity of your algorithm. Do people at the table agree?

  4. Formally demonstrate how your growth function fits that time-complexity. Consider both big-O and big-$\Omega$ (and, thus, big-$\Theta$).

  5. If you have extra time, consider the best-case time complexity! When does that occur?

  6. For credit: Submit some artifact of your work to Moodle, including, at least, the growth function and the time complexity (in Big-Oh) that you found.

results matching ""

    No results matching ""