Time complexity measures how an algorithm’s execution time grows with input size n; memory or space complexity measures its storage requirements. section 1.0
Use asymptotic runtime to compare algorithms and match them to input constraints:
- A linear scan searches an array in O(n), while binary search uses a sorted array to achieve O(log n). section 4.1.1
- Selection sort and insertion sort take O(n²), making them suitable mainly for small inputs. section 4.1.1
- Merge sort, heap sort, and quicksort generally take O(n log n); their runtime follows the height of a complete binary-tree representation. section 4.1.1
- Count sort, radix sort, and bucket sort can reach O(n) under additional input constraints, such as integers from a small range. section 4.1.1
Efficient implementations depend on both data structures and algorithmic complexity. Stacks support O(1) push and pop, queues support O(1) enqueue and dequeue, and linked lists retain O(n) search. Distributed computation can reduce runtime further. section 1.5 section 4.1.1
Performance checks
Evaluate an algorithm by computing both runtime and memory complexity. Concrete exercises include analyzing Bernoulli naive Bayes and computing PCA runtime. section 5.7 section 8.4
