Algorithms: Big O efficiency, searching, sorting and recursion

Learning objectives

Describe the time and space complexity of an algorithm in Big O notation, such as O(1), O(log n), O(n) and O(n²), and use it to judge how the algorithm scales

Construct and trace linear search and binary search, state that binary search needs sorted data, and compare their efficiency for a given data set

Construct and trace bubble sort and selection sort from their own loops, comparisons and swaps (so that they still work when a question rules out built-in helpers such as sort, max or min), showing the list after each pass, and evaluate their time and space complexity

(HL) Explain recursion through the base case, the recursive case and the call stack, and discuss its uses in quicksort, fractals and tree traversal against its cost in memory and complexity compared with iteration

(HL) Construct and trace simple non-branching recursive methods in Java or Python, recording every call made and every value returned