Time and space complexity analysis (big-O notation)

Explore the hierarchy of time and space complexities, from constant to factorial, and learn how O(1), O(log n), O(n), O(n log n), and O(n^k) guide algorithm efficiency.

Learn to analyze an algorithm's time and space complexity using big-O, big-Omega, and big-Theta, by expressing resource usage, removing constants, and comparing terms for single and multi-input cases.

Explore amortized complexity with a dynamic array insert example, showing how rare costly resizes keep the average cost low and contrasting amortized with average case analysis.

Compare algorithms by time and space complexity (big-O), account for the hidden constant, and assess trade-offs across input sizes and cases to choose by time or space priority.

Analyze three approaches to the 'find pair that sums up to k' problem: brute-force, two-pointer after sorting, and hash-set. Compare time and space complexities for best, worst, and average cases.

Explore the linear search algorithm, which traverses a list to find a target and returns its index or -1. Compare its complexity, with worst-case O(n), best-case O(1), and space Theta(1).

Apply binary search to sorted data, such as weight-sorted watermelons, by checking the middle item and discarding halves, yielding O(logn) time and Theta(1) space.

Master Knuth-Morris-Pratt string search by building the LPS array and using it to skip mismatches, achieving linear time. Understand time and space implications in practical analysis.

Explore sorting algorithms and their properties, including comparison-based vs non-comparison-based methods, stability, recursion, in-place, adaptive, and online traits, and how comparison keys affect sorting and time and space complexity.

Explore insertion sort and analyze its time and space complexity, including worst and average O(n^2) time, best O(n) time, O(1) space, and properties like stable, adaptive, and in-place operation.

Compare adjacent elements, swap when out of order, and progressively grow the sorted portion from the unsorted array, with worst-case and average-case O(n^2) time, best-case O(n), and O(1) space.

Explore selection sort, which searches for the minimum from the unsorted tail and swaps it into place, achieving O(n^2) time in all cases with O(1) space, non-recursive and not adaptive.

Explore how merge sort splits and merges arrays, recursively sorts subparts, and yields a sorted list with O(n log n) time and O(n) space, noting its stability and non-adaptive nature.

Learn how heapsort uses a binary min-heap to insert elements and repeatedly extract the root, which is smallest, sorting in place with time complexity n log n and constant space.

Master quicksort by partitioning around a pivot with left and right pointers, swapping elements, and recursively sorting subarrays; analyze O(n log n) best/average and O(n^2) worst with O(log n) space.

Create a count array, count occurrences, compute the cumulative sum, and insert elements from the end to their sorted positions, yielding a stable, non-comparison based sort with O(n+k) time.

Radix sort sorts digits from the right using counting sort per digit with zero-padding, giving O(d(n+b)) time and O(n+b) space, and remaining stable and non-comparison-based.

Bucket sort distributes elements into k buckets via floor(k * elem / (max+1)), sorts each bucket, then concatenates. Best/average time is O(n+k); worst is O(n^2), with space O(n+k).

Explore shell sort, an in-place, adaptive, comparison-based sorting method that uses gap sequences to accelerate insertion sort. Analyze its time complexity across best and worst cases and its space efficiency.

Explore time complexity of recursive algorithms using recursion tree, recurrence relation, and Master theorem, detailing splitting costs, solving subproblems, and combining results, with merge sort as an example.

Analyze recursive time complexity with the recursion tree method. Draw the tree, sum split and base costs, and derive cases like log n, n log n, and 2^n.

Identify the time complexity of recursive functions by applying the recurrence relation method, deriving T(n) from base cases and recursive costs, with examples like factorial, binary search, and merge sort.

Apply the master theorem to identify time complexity for recurrences of the form T(n)=aT(n/b)+f(n) by comparing c with log_b(a) and using the extended cases for f(n)=n^c(log n)^d.

Analyze the space complexity of recursive functions by focusing on max memory usage, stack frames, and local variables, illustrated with merge sort and compared to time complexity.

Explore memoization, using a lookup map to cache recursive results, create keys from changing parameters, and avoid repeated work, reducing time complexity from O(m^n) to O(nm) with extra space.

Learn how dynamic programming converts recursive problems into iterative tabulation by exploiting optimal substructure and overlapping subproblems. See how this applies to Fibonacci, lcs, and ways to climb stairs.

Explore how dynamic and static arrays affect time complexity of insert, delete, access, search, and sort, with amortized costs and practical choices for Python lists and C++ vectors.

Explore the time complexity of linked lists, stacks, and queues, covering insertions, deletions, access, search, and sort, with notes on head, tail, and singly or doubly linked lists.

Explore hash tables and sets, including hashing, collisions, and linked lists, enabling efficient insert, search, and remove in O(1) average. Apply to removing duplicates and finding intersections.

Explore the tree data structure and its main operations across k-ary trees, binary trees, binary search trees, self-balancing binary search trees, and heaps, with time complexities including O(logn) and O(n).

Explore graphs through adjacency list and adjacency matrix representations, compare time and space complexities for edge checks, additions, removals, and vertex operations on vertices and edges, with big-O insights.

Identify common mistakes in complexity analysis, such as confusing variable names and misnaming input sizes. Use sizes n and m, consider worst, best, and average cases, and seek tight bounds.

Discover why you don't always optimize time and space complexity. Consider five reasons: absence of necessity, time cost, asymptotically smaller isn't always faster, complexity, and impossibility, especially for small inputs.

Analyze two solutions to the first repeating character problem: a brute-force nested-loop approach with O(n^2) time and O(1) space, and a set-based approach with O(n) time and O(n) space.

Analyze three approaches to the maximum subarray problem and compare their time and space costs: brute force, O(n^2) cumulative sum, and Kadane's O(n) algorithm.

Analyze two peak finding solutions: a linear scan with O(n) time and a divide-and-conquer binary search with O(log n) time, both using constant space and -inf edge handling.

Compare two approaches to detect palindromes in a singly linked list, highlighting a O(n^2) time, O(1) space method and a faster O(n) time, O(1) space solution using slow–fast pointers.

Analyze the time and space complexity of generating all subsequences of a string using binary inclusion choices. Show the algorithm operates in O(n2^n) time and O(n2^n) space.

Explore the minimum cost path problem by contrasting a recursive, exponential solution with a dynamic programming approach using a dp matrix to achieve O(nm) time and space.

Explore five solutions to the longest consecutive sequence problem, analyze their time and space complexities from O(n^3) to O(n), and learn efficient techniques using sets and sorting.

Explore three approaches to the longest common subsequence problem, including brute force, a non-optimized recursive approach, and the dynamic programming method, with their time and space complexities.

Analyze two approaches to counting subsets that sum to k: a backtracking recursive method with O(2^n) time and a memoized solution achieving O(nk) time and O(nk) space.

Compare two approaches for binary tree balance by height difference. Compare first using dfs height calculations with O(n log n) time, and compare second achieving O(n) time and O(h) space.

Explore the time and space complexity of generating all distinct permutations of an array using a recursive approach, including base case handling, duplicates avoidance, and n! growth.

Analyze word search on a character board via a recursive process with a visited set, forming the word from adjacent cells using four-direction exploration and O(nm4^w) time, O(w) space.

Explore the n-queens problem solved by backtracking to count valid placements on an n by n board. Analyze time complexity O(n^2 n!) and space complexity O(n^2).

Learn how to reduce space complexity in dynamic programming from o(nm) to o(m) by using two rows instead of a full matrix, illustrated with the longest common subsequence.