Insertion sort complexity

best: O(n) worst: O(n^2) space complexity: O(1)

Bubble sort complexity

best: O(n^2) worst: O(n^2) Space complexity: O(1)

Merge sort complexity

best: O(nlogn) worst: O(nlogn) space complexity: O(n)

Quick sort complexity

best: O(nlogn) worst: O(nlogn) space complexity: O(logn)

Linear search complexity

best: O(1) worst: O(n) space complexity: O(1)

Binary search complexity

best: O(1) wost: O(logn) space complexity: O(1)

How does selection sort work?

Repeatedly find the smallest element and place it at the beginning. Steps: Assume the first element is the minimum. Scan the rest of the array to find the actual smallest value. Swap it with the first element. Move to the next position and repeat.

How does insertion sort work?

Build a sorted list one element at a time. Steps: Take the next element (key). Compare it with elements before it. Shift larger elements to the right. Insert the key in the correct position.

How does bubble sort work?

Repeatedly swap adjacent elements if they are in the wrong order. Steps: Compare two neighboring elements. Swap them if needed. Continue across the array. Repeat passes until sorted.

How does merge sort work?

Divide and conquer. Steps: Split the array into two halves. Recursively sort each half. Merge the sorted halves together.

How does quick sort work?

Use a pivot to divide the array. Steps: Choose a pivot element. Move smaller elements to the left. Move larger elements to the right. Recursively sort both sides.

How does linear search work?

Check each element one by one until the target is found. Steps: Start at index 0. Compare each value to the target. Stop when found or when the array ends.

How does binary search work?

Repeatedly divide a sorted array in half. Steps: Find the middle element. Compare it with the target. If target is smaller → search left half. If larger → search right half. Repeat until found or range disappears.

Help

Options

focusNode

Didn't know it?
click below

Knew it?
click below

Don't Know

Remaining cards (0)

Know

retry

shuffle

restart

0:00

Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.

Normal Size Small Size show me how

lab exam 2

Question	Answer
Selection sort complexity	best: O(n^2) worst: O(n^2)
Insertion sort complexity	best: O(n) worst: O(n^2) space complexity: O(1)
Bubble sort complexity	best: O(n^2) worst: O(n^2) Space complexity: O(1)
Merge sort complexity	best: O(nlogn) worst: O(nlogn) space complexity: O(n)
Quick sort complexity	best: O(nlogn) worst: O(nlogn) space complexity: O(logn)
Linear search complexity	best: O(1) worst: O(n) space complexity: O(1)
Binary search complexity	best: O(1) wost: O(logn) space complexity: O(1)
How does selection sort work?	Repeatedly find the smallest element and place it at the beginning. Steps: Assume the first element is the minimum. Scan the rest of the array to find the actual smallest value. Swap it with the first element. Move to the next position and repeat.
How does insertion sort work?	Build a sorted list one element at a time. Steps: Take the next element (key). Compare it with elements before it. Shift larger elements to the right. Insert the key in the correct position.
How does bubble sort work?	Repeatedly swap adjacent elements if they are in the wrong order. Steps: Compare two neighboring elements. Swap them if needed. Continue across the array. Repeat passes until sorted.
How does merge sort work?	Divide and conquer. Steps: Split the array into two halves. Recursively sort each half. Merge the sorted halves together.
How does quick sort work?	Use a pivot to divide the array. Steps: Choose a pivot element. Move smaller elements to the left. Move larger elements to the right. Recursively sort both sides.
How does linear search work?	Check each element one by one until the target is found. Steps: Start at index 0. Compare each value to the target. Stop when found or when the array ends.
How does binary search work?	Repeatedly divide a sorted array in half. Steps: Find the middle element. Compare it with the target. If target is smaller → search left half. If larger → search right half. Repeat until found or range disappears.

Created by: jayne_

"Know" box contains:
Time elapsed:
Retries: