Curriculum Portal

neurologyYou need to know

• Algorithm choice depends on data size, data order, and required speed.
• Linear search works on unsorted lists by checking items sequentially.
• For a list of `n` items, a worst-case linear search makes `n` comparisons.
• Binary search requires data to be sorted first.
• Binary search halves the remaining search space each step.
• Binary search compares the target with the middle item, discards the half in which the target cannot occur, and repeats until the target is found or the search space is empty.
• The worst-case number of comparisons made by binary search grows logarithmically as the list size increases.
• Bubble sort compares adjacent items and swaps when out of order.
• Each bubble sort pass places one largest unsorted value at the end.
• The worst-case work of bubble sort and insertion sort grows approximately with the square of the list size.
• Traces can count comparisons and swaps as evidence.
• Insertion sort builds a sorted section one item at a time.
• Insertion sort is often efficient for small or nearly sorted lists.
• Step counts reveal how performance changes as dataset size increases.
• Fair timing comparisons keep conditions consistent (same device/load, repeated runs, and comparable datasets).
• Timing tests can support comparisons but should be interpreted alongside trace evidence because device speed and background load affect timings.

• Trace search and sort algorithms accurately on lists.
• Implement simple search/sort algorithms in Python using list indexing and loops.
• Choose an appropriate algorithm for a specific context.
• Justify algorithm choice using evidence from traces, step counts, and practical tests.