← Public decks·Computer Science

Big-O Notation and Asymptotic Complexity for Arrays, Lists, Trees, and Hashes

Time and space complexity for operations on arrays, linked lists, hash tables, BSTs, heaps, and sorting algorithms using Big-O notation.

11 cards· by GuruOwl

Make a deck like this from your own PDF — free.

Try it
  1. 01
    Big-O notation describes the upper bound on the growth rate of an algorithm's resource consumption as input size n approaches infinity.
    It ignores constant factors and lower-order terms to focus on the dominant growth trend.
    Flashify::Big-O_Notation
  2. 02
    Accessing an array element by index is O(1), while searching an unsorted array is O(n).
    Random access is constant time because memory is contiguous; searching requires a linear scan.
    Flashify::Data_Structures::Arrays
  3. 03
    Inserting or deleting at an arbitrary position in an array is O(n) because it requires shifting elements.
    Appending at the end is amortized O(1) if capacity is managed with doubling.
    Flashify::Data_Structures::Arrays
  4. 04
    In a singly-linked list, insertion or deletion after a known node is O(1).
    This is because only pointers need to be updated, unlike arrays which require shifting.
    Flashify::Data_Structures::LinkedLists
  5. 05
    Hash tables achieve average-case O(1) for insert, delete, and lookup, but worst-case is O(n).
    Worst-case O(n) occurs with pathological collisions where many keys map to the same bucket.
    Flashify::Data_Structures::HashTables
  6. 06
    Balanced binary search trees (e.g., AVL or Red-Black) support search, insert, and delete in O(log n) for both average and worst cases.
    Unbalanced BSTs can degenerate to O(n) if the input is sorted.
    Flashify::Data_Structures::Trees
  7. 07
    In a binary heap, the time complexity for insert and extract-min/max is O(log n), while find-min/max is O(1).
    Building a heap from an existing array (heapify) is O(n).
    Flashify::Data_Structures::Heaps
  8. 08
    The comparison-based sorting lower bound is Ω(n log n).
    Algorithms like Merge Sort and Heap Sort meet this lower bound in the worst case.
    Flashify::Algorithms::Sorting
  9. 09
    Quicksort has an average time complexity of O(n log n) but a worst-case of O(n^2).
    Worst-case performance is typically mitigated by using randomization or median-of-three pivot selection.
    Flashify::Algorithms::Sorting
  10. 10
    Insertion sort is O(n^2) in the worst case but performs at O(n) on nearly sorted data.
    This makes it efficient for small datasets or datasets that are already mostly in order.
    Flashify::Algorithms::Sorting
  11. 11
    Amortized analysis explains why dynamic arrays and hash tables appear to have constant time operations despite occasional expensive resizing.
    It spreads the cost of high-latency operations over many low-cost operations.
    Flashify::Complexity_Analysis