Complexity Analysis and Core Patterns

Explain Big-O, Big-Omega, and Big-Theta notations for describing algorithm performance.

Determine the time and space complexity of iterative algorithms, including those with nested loops.

Compare common complexity classes (O(1), O(log n), O(n), O(n log n), O(n²), O(2^n)) with concrete examples.

Apply amortized analysis to explain the time complexity of operations like dynamic array resizing.

Apply the two-pointer technique to solve problems on sorted arrays and strings (e.g., two-sum, valid palindrome).

Apply the sliding window technique to find optimal subarrays or substrings (e.g., max sum subarray of size k).

Use prefix sums to answer range sum queries in O(1) time after O(n) preprocessing.

Solve in-place array manipulation problems (e.g., rotate an array, move zeroes).