Exit Ticket: Day 27 - Algorithm Analysis, Sorting

day27-exit-ticket.md

Exit Ticket: Day 27 - Algorithm Analysis, Sorting

You should be able to:

• Articulate the difference between an algorithm and a heuristic
• Explain Big O in terms of both time and space (when/how is it useful, what does it measure, etc.)
• Describe how both Bubble Sort and Merge Sort operate, as well as discuss their time/space complexities

In your own words, what is Big O measuring?

• It classifies algorithms according to how their runtime or space requirements grow as the input size grows in the worst case scenario.

Which Big O represents the fastest growth curve (i.e. the slowest runtime)?

• O(n)
• O(n²)
• O(n * log(n))
• O(n!) ☑️

Which Big O represents the slowest growth curve (i.e. the fastest runtime)?

• O(log(n))
• O(n)
• O(n²)
• O(1) ☑️

Which is the faster sorting algorithm?

• Bubble sort
• Merge sort ☑️

What is the best Big O of a sorting algorithm?

• O(n * log(n))

Describe the conceptual approach behind merge sort.

Top Down Approach (Recursive)

1. If array is one element, good job it’s sorted!
2. Otherwise, split the array and merge sort each half.
3. Merge combined halves into sorted whole.

Bottom Up Approach (Iterative)

1. Divide array of n elements into n arrays of 1 element.
2. Merge neighboring arrays in sorted order.
3. Repeat step 2 until there’s only one array.

---

References:

• Big-O Cheat Sheet