2.3.1(f) Big O Do Now

Emily is learning about sorting algorithms in her computer science class. She wonders if Bubble Sort is an example of a divide and conquer sorting algorithm?

• True

• False

Isabelle is sorting her collection of books using Bubble Sort. What is the worst-case time complexity of this sorting algorithm?

• O(n log n)

• O(n)

• O(n^2)

• O(1)

Answer explanation

Bubble Sort has a worst-case time complexity of O(n^2) due to its nested loops that compare and swap elements.

Match the following

• Quick Sort

• Picks a pivot and partitions the array around it

• Merge Sort

• Divides the array into two halves and merges them after sorting

• Bubble Sort

• Works well with almost sorted datasets

• Insertion Sort

• Worst-case time complexity is O(n^2)

Big O Notation

e

f

g

h

Quick Sort

Bubble Sort

A* Algorithm

Binary Search

Linear Search

Merge Sort

Insertion Sort

Dijkstra’s Shortest Path Algorithm

Match the following

• Dijkstra’s Shortest Path Algorithm

• Requires the array to be sorted before searching

• A* Algorithm

• Time complexity is O(n) for average and worst cases

• Binary Search

• Uses a heuristic to guide its search

• Linear Search

• Uses a priority queue to find the shortest path