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 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).

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 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.

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.

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.

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.

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 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.

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.

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.

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).