Chapter 13 — Recursive Algorithms for Speed

0.0(0)
Studied by 0 people
call kaiCall Kai
Locked
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/14

encourage image

There's no tags or description

Looks like no tags are added yet.

Last updated 3:06 PM on 8/28/26
Name
Mastery
Learn
Test
Matching
Spaced
Call with Kai
Chat

No analytics yet

Send a link to your students to track their progress

15 Terms

1
New cards
Divide-and-conquer
Break a problem into smaller parts and solve them
2
New cards
Partitioning
Move values lower than pivot to one side and higher values to the other
3
New cards
Pivot
The value used to divide the array
4
New cards
Correct pivot position
Where the pivot belongs after partitioning
5
New cards
Partition Big O
O(N)
6
New cards
Quicksort
Partition the array, then recursively sort each side
7
New cards
Quicksort base case
A subarray with zero or one element is already sorted
8
New cards
Quicksort average Big O
O(N log N)
9
New cards
Quicksort worst case
O(N²), when partitions are consistently unbalanced
10
New cards
Balanced partition
Pivot splits data roughly evenly
11
New cards
Unbalanced partition
One side gets most values
12
New cards
Quickselect
Finds a ranked value without fully sorting
13
New cards
Quickselect key idea
Only recurse into the side containing the desired index
14
New cards
Quickselect average Big O
O(N)
15
New cards
OA clue
Quicksort sorts both sides; Quickselect follows one sid